有没有哪位大佬看得出来为什么第三个题会超时?
查看原帖
有没有哪位大佬看得出来为什么第三个题会超时?
1123721
lishunjie楼主2024/11/28 20:16
//杉月
#include<bits/stdc++.h>
#define N 200005
//#define double   long double
//#define int  long long
using namespace std;
typedef long long LL;
int lowbit(int x){return x&(-x);}
int n;
int ans;
int c[N],rr[N];
void add(int x,int y){
	for(int i=x;i<=N;i+=lowbit(i)){
	     c[i]+=y;
	}
}

int sum(int x){
	if(x<=0) return -1;
	int res=0;
	for(int i=x;i;i-=lowbit(i)){
		res+=c[i];
	}
	return res;
}

signed main(){
	//freopen("detect2.in","r",stdin);
	//freopen("detect.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
		char temp;
		cin>>temp;
		if(temp=='A'){
			int z,y,anss=0;
			cin>>z>>y;
			while(1){
				int l=1,r=y;
			int mid=1;
			while(l<=r){
				mid=(l+r)>>1;
				if(sum(mid)<sum(y)){
					l=mid+1;
				}else{
					if(sum(mid-1)<sum(y)) break;
					r=mid-1;
				}
			}
			if(rr[mid]>=z){
				add(mid,-1);
				anss++;
				ans--;
			}else break;
			}
        
        add(z,1);
        rr[z]=y;ans++;
        
        cout<<anss<<endl;
		}
		else{
			cout<<ans<<endl;
		}
	}
	//fclose(stdin);
	//fclose(stdout);
    return 0;
}

给孩子写无语了

2024/11/28 20:16
加载中...