Submission #649869

#	Time	Username	Problem	Language	Result	Execution time	Memory
649869		rsjw	Growing Trees (BOI11_grow)	C++17	100 / 100	81 ms	5888 KiB

grow

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int n;
int t[100010],a[100010];
void update(int x,int I) {
	while(x<=n+1) t[x]+=I,x+=x&-x;
}
int query(int x) {
	int ans=0; while(x) ans+=t[x],x-=x&-x; return ans;
}
//写个假的二分
int search_lower(int x) { //第一个大于等于x 
	int l=1,r=n,mid;
	while(l<=r) {
		mid=(l+r)/2;
		if(query(mid)<x) l=mid+1;
		else r=mid-1;
	}
	return r+1;
}
int search_upper(int x) { //第一个大于x 
	int l=1,r=n,mid;
	while(l<=r) {
		mid=(l+r)/2;
		if(query(mid)<=x) l=mid+1;
		else r=mid-1;
	}
	return r+1;
}
signed main() {
	// freopen("1.in","r",stdin);
	int m,i,j;
	char c;
	int x,y,t,t1,t2,tt;
	fin>>n>>m;
	for(i=1;i<=n;i++) fin>>a[i];
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++) update(i,a[i]-a[i-1]);
	for(i=1;i<=m;i++) {
		fin>>c>>x>>y;
		if(c=='F') {
			t=search_lower(y);
			if(t+x-1>n) {
				update(t,1);
				update(n+1,-1);
			} else {
				tt=query(t+x-1);
				t1=search_lower(tt);
				t2=search_upper(tt)-1;
				update(t,1);
				update(t1,-1);
				update(t2-(x-t1+t)+1,1);
				update(t2+1,-1);
			}
			
		} else {
			fout<<search_upper(y)-search_lower(x)<<'\n';
		}
	}
	return 0;
}

Compilation message (stderr)

grow.cpp: In member function 'IO& IO::operator<<(T)':
grow.cpp:22:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   22 |         while(st[0]) pc('0'+st[st[0]--]);return *this;
      |         ^~~~~
grow.cpp:22:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   22 |         while(st[0]) pc('0'+st[st[0]--]);return *this;
      |                                          ^~~~~~
grow.cpp: In function 'int main()':
grow.cpp:54:10: warning: unused variable 'j' [-Wunused-variable]
   54 |  int m,i,j;
      |          ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10