oj.uz

Submission #649869

# Submission time Handle Problem Language Result Execution time Memory
649869 2022-10-11T13:31:07 Z rsjw Growing Trees (BOI11_grow) C++17
100 / 100
 81 ms 5888 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4068 KB Output is correct
2 Correct 81 ms 5140 KB Output is correct
3 Correct 34 ms 5000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 372 KB Output is correct
5 Correct 30 ms 2508 KB Output is correct
6 Correct 34 ms 2960 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 11 ms 1876 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2764 KB Output is correct
2 Correct 36 ms 3236 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 18 ms 2332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3456 KB Output is correct
2 Correct 41 ms 3024 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 38 ms 3148 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3396 KB Output is correct
2 Correct 72 ms 4224 KB Output is correct
3 Correct 11 ms 1492 KB Output is correct
4 Correct 34 ms 4152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3416 KB Output is correct
2 Correct 73 ms 4344 KB Output is correct
3 Correct 34 ms 4692 KB Output is correct
4 Correct 12 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3820 KB Output is correct
2 Correct 43 ms 4304 KB Output is correct
3 Correct 42 ms 4948 KB Output is correct
4 Correct 12 ms 1360 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4556 KB Output is correct
2 Correct 72 ms 4112 KB Output is correct
3 Correct 19 ms 3284 KB Output is correct
4 Correct 43 ms 4092 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4296 KB Output is correct
2 Correct 78 ms 5052 KB Output is correct
3 Correct 81 ms 5604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5888 KB Output is correct