社区讨论

此处cin和getchar()和scanf对答案有什么影响吗

学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo1m3r75
此快照首次捕获于
2023/10/22 23:16
2 年前
此快照最后确认于
2023/11/03 00:01
2 年前
查看原帖
使用cin输入opt可ac
另外两个都是全wa的
请教这有什么区别吗
CPP
// Problem: P1486 [NOI2004] 郁闷的出纳员
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1486
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: fzy
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
#define int ll

const int maxn=1e5+10;
const int inf=1e9+7;
int n,low,ans;

inline int read() {
    int s=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)) {
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int root=0;
int son[maxn][2],siz[maxn],num[maxn],val[maxn],pri[maxn],tot=0;
mt19937 rnd(time(0));

inline void pushup(int rt) {
	siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+num[rt];
}

inline void rotate(int &rt,int d) { // 0右 1左
	int t=son[rt][d];
	son[rt][d]=son[t][d^1];
	son[t][d^1]=rt;
	pushup(rt),pushup(t);
	rt=t;
}

inline void insert(int &rt,int k) {
	if(!rt) {
		rt=++tot;
		siz[rt]=num[rt]=1;
		pri[rt]=rnd();
		val[rt]=k;
		return;
	}
	if(val[rt]==k) {
		num[rt]++;
		siz[rt]++;
		return;
	}
	int d=(val[rt]<k);
	insert(son[rt][d],k);
	if(pri[rt]>pri[son[rt][d]]) rotate(rt,d);
	pushup(rt);
}

inline void del(int &rt,int k) {
	if(!rt) return;
	if(val[rt]<k) del(son[rt][1],k);
	else if(val[rt]>k) del(son[rt][0],k);
	else {
		if(num[rt]>1) num[rt]--,siz[rt]--;
		else if(!son[rt][0]||!son[rt][1]) rt=son[rt][0]+son[rt][1];
		else {
			int d=(pri[son[rt][0]]>pri[son[rt][1]]);
			rotate(rt,d);
			del(rt,k);
		}
	}
	pushup(rt);
}

inline int findpre(int rt,int k) {
	if(!rt) return -inf;
	if(val[rt]<k) return max(val[rt],findpre(son[rt][1],k));
	else return findpre(son[rt][0],k);
}

inline int findkth(int rt,int k) {
	if(!rt) return 0;
	if(k>siz[son[rt][0]]+num[rt]) 
		return findkth(son[rt][1],k-siz[son[rt][0]]-num[rt]);
	else if(k<=siz[son[rt][0]]) return findkth(son[rt][0],k);
	else return val[rt];
}

signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    n=read(),low=read();
    int add=0,in=0;
    while(n--) {
    	char opt;
    	cin>>opt; //这里用cin和scanf和getchar有区别吗
    	int x=read();
    	if(opt=='I') {
    		if(x-add>=low) insert(root,x-add),in++;
    	}
    	else if(opt=='A') low-=x,add+=x;
    	else if(opt=='S') {
    		low+=x,add-=x;
    		int tmp=low;
    		while(findpre(root,tmp)!=-inf) {
    			int temp=findpre(root,tmp);
    			del(root,temp);
    		}
    	}
    	else if(opt=='F'){
    		if(siz[root]<x) puts("-1");
    		else write(findkth(root,siz[root]-x+1)+add),puts("");
    	}
    }
    write(in-siz[root]),puts("");
    return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...