oj.uz

답안 #650100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650100 2022-10-12T12:18:49 Z rsjw Growing Trees (BOI11_grow) C++17
100 / 100
 42 ms 5604 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) 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=0,sum=0,i;
	for(i=17;i>=0;i--) {
		if(l+(1<<i)<=n&&sum+t[l+(1<<i)]<x) l+=(1<<i),sum+=t[l];
	}
	return l+1;
}
int search_upper(int x) { //第一个大于x 
	int l=0,sum=0,i;
	for(i=17;i>=0;i--) {
		if(l+(1<<i)<=n&&sum+t[l+(1<<i)]<=x) l+=(1<<i),sum+=t[l];
	}
	return l+1;
}
signed main() {
	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:48:10: warning: unused variable 'j' [-Wunused-variable]
   48 |  int m,i,j;
      |          ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3256 KB Output is correct
2 Correct 36 ms 5048 KB Output is correct
3 Correct 25 ms 5000 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 12 ms 2444 KB Output is correct
6 Correct 16 ms 2880 KB Output is correct
7 Correct 3 ms 520 KB Output is correct
8 Correct 10 ms 1876 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2004 KB Output is correct
2 Correct 16 ms 3180 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 14 ms 2268 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 2348 KB Output is correct
2 Correct 17 ms 3072 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 16 ms 3152 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2636 KB Output is correct
2 Correct 33 ms 4212 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Correct 22 ms 4180 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 2672 KB Output is correct
2 Correct 33 ms 4328 KB Output is correct
3 Correct 26 ms 4692 KB Output is correct
4 Correct 6 ms 1324 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2868 KB Output is correct
2 Correct 26 ms 4348 KB Output is correct
3 Correct 29 ms 4920 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 3532 KB Output is correct
2 Correct 31 ms 4180 KB Output is correct
3 Correct 14 ms 3296 KB Output is correct
4 Correct 29 ms 4072 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 3420 KB Output is correct
2 Correct 36 ms 5032 KB Output is correct
3 Correct 38 ms 5604 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 4656 KB Output is correct