社区讨论
此处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 条回复,欢迎继续交流。
正在加载回复...