oj.uz

Submission #25054

# Submission time Handle Problem Language Result Execution time Memory
25054 2017-06-20T05:29:12 Z zigui Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1506 ms 66664 KB 
#include <cstdio>
typedef long long lint;

int n, q, k;
int a[100005];

struct bit{
	lint tree[100005];
	int lim;
	void init(int n){
		lim = n + 2;
	}
	void add(int x, lint v){
		x += 2;
		while(x <= lim){
			tree[x] += v;
			x += x & -x;
		}
	}
	lint sum(int x){
		x += 2;
		lint ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
	lint rsum(int s, int e){
		return sum(e) - sum(s-1);
	}
}bit;

void solve3(){
	bit.init(n);
	for (int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
		bit.add(i,a[i]);
	}
	for (int i=0; i<q; i++) {
		int t;
		scanf("%d",&t);
		if(t == 1){
			int u, b;
			scanf("%d %d",&u,&b);
			bit.add(u,b - a[u]);
			a[u] = b;
		}
		if(t == 2){
			scanf("%*d %*d");
		}
		if(t == 3){
			int s,e;
			scanf("%d %d",&s,&e);
			printf("%lld\n",bit.rsum(s,e));
		}
	}
}

struct seg{
	lint tree[270000][30];
	int lazy[270000];
	void lazydown(int p){
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		for(int i=0; i<30; i++){
			if(i + lazy[p] < 30) tree[2*p][i] = tree[2*p][i + lazy[p]];
			else tree[2*p][i] = 0;
			if(i + lazy[p] < 30) tree[2*p+1][i] = tree[2*p+1][i + lazy[p]];
			else tree[2*p+1][i] = 0;
		}
		lazy[p] = 0;
		for(int i=0; i<30; i++){
			tree[p][i] = tree[2*p][i] + tree[2*p+1][i];
		}
	}
	void add(int pos, int ps, int pe, int p, int v){
		if(ps == pe){
			lazy[p] = 0;
			tree[p][0] = v;
			for (int i=1; i<30; i++){
				tree[p][i] = tree[p][i-1] / k;
			}
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		if(pos <= pm) add(pos,ps,pm,2*p,v);
		else add(pos,pm+1,pe,2*p+1,v);
		for (int i=0; i<30; i++){
			tree[p][i] = tree[2*p][i] + tree[2*p+1][i];
		}
	}
	void move(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			lazy[p]++;
			for(int i=0; i<29; i++){
				tree[p][i] = tree[p][i+1];
			}
			tree[p][29] = 0;
			return;
		}
		lazydown(p);
		int pm = (ps + pe) / 2;
		move(s,e,ps,pm,2*p);
		move(s,e,pm+1,pe,2*p+1);
		for(int i=0; i<30; i++){
			tree[p][i] = tree[2*p][i] + tree[2*p+1][i];
		}
	}
	lint sum(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return 0;
		if(s <= ps && pe <= e) return tree[p][0];
		lazydown(p);
		int pm = (ps + pe) / 2;
		lint ret = sum(s,e,ps,pm,2*p) + sum(s,e,pm+1,pe,2*p+1);
		for(int i=0; i<30; i++){
			tree[p][i] = tree[2*p][i] + tree[2*p+1][i];
		}
		return ret;
	}
}seg;

int main(){
	scanf("%d %d %d",&n,&q,&k);
	if(k == 1){
		solve3();
		return 0;
	}
	else{
		for (int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
			seg.add(i,1,n,1,a[i]);
		}
		for (int i=0; i<q; i++) {
			int t;
			scanf("%d",&t);
			if(t == 1){
				int u, b;
				scanf("%d %d",&u,&b);
				seg.add(u,1,n,1,b);
			}
			if(t == 2){
				int s,e;
				scanf("%d %d",&s,&e);
				seg.move(s,e,1,n,1);
			}
			if(t == 3){
				int s,e;
				scanf("%d %d",&s,&e);
				printf("%lld\n",seg.sum(s,e,1,n,1));
			}
		}
	}
}

Compilation message

sterilizing.cpp: In function 'void solve3()':
sterilizing.cpp:37:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
sterilizing.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
                 ^
sterilizing.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&u,&b);
                        ^
sterilizing.cpp:50:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%*d %*d");
                    ^
sterilizing.cpp:54:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&s,&e);
                        ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:126:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&q,&k);
                            ^
sterilizing.cpp:133:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i]);
                     ^
sterilizing.cpp:138:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&t);
                  ^
sterilizing.cpp:141:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&u,&b);
                         ^
sterilizing.cpp:146:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&s,&e);
                         ^
sterilizing.cpp:151:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&s,&e);
                         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 66664 KB Output is correct
2 Correct 0 ms 66664 KB Output is correct
3 Correct 3 ms 66664 KB Output is correct
4 Correct 13 ms 66664 KB Output is correct
5 Correct 19 ms 66664 KB Output is correct
6 Correct 16 ms 66664 KB Output is correct
7 Correct 19 ms 66664 KB Output is correct
8 Correct 19 ms 66664 KB Output is correct
9 Correct 9 ms 66664 KB Output is correct
10 Correct 19 ms 66664 KB Output is correct
11 Correct 19 ms 66664 KB Output is correct
12 Correct 19 ms 66664 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 66664 KB Output is correct
2 Correct 46 ms 66664 KB Output is correct
3 Correct 53 ms 66664 KB Output is correct
4 Correct 63 ms 66664 KB Output is correct
5 Correct 86 ms 66664 KB Output is correct
6 Correct 73 ms 66664 KB Output is correct
7 Correct 86 ms 66664 KB Output is correct
8 Correct 76 ms 66664 KB Output is correct
9 Correct 76 ms 66664 KB Output is correct
10 Correct 79 ms 66664 KB Output is correct
11 Correct 79 ms 66664 KB Output is correct
12 Correct 69 ms 66664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 66664 KB Output is correct
2 Correct 269 ms 66664 KB Output is correct
3 Correct 293 ms 66664 KB Output is correct
4 Correct 769 ms 66664 KB Output is correct
5 Correct 1466 ms 66664 KB Output is correct
6 Correct 1339 ms 66664 KB Output is correct
7 Correct 56 ms 66664 KB Output is correct
8 Correct 1419 ms 66664 KB Output is correct
9 Correct 1012 ms 66664 KB Output is correct
10 Correct 999 ms 66664 KB Output is correct
11 Correct 943 ms 66664 KB Output is correct
12 Correct 946 ms 66664 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 66664 KB Output is correct
2 Correct 989 ms 66664 KB Output is correct
3 Correct 559 ms 66664 KB Output is correct
4 Correct 909 ms 66664 KB Output is correct
5 Correct 1443 ms 66664 KB Output is correct
6 Correct 1359 ms 66664 KB Output is correct
7 Correct 1463 ms 66664 KB Output is correct
8 Correct 1506 ms 66664 KB Output is correct
9 Correct 996 ms 66664 KB Output is correct
10 Correct 1056 ms 66664 KB Output is correct
11 Correct 1026 ms 66664 KB Output is correct
12 Correct 979 ms 66664 KB Output is correct