oj.uz

Submission #25053

# Submission time Handle Problem Language Result Execution time Memory
25053 2017-06-20T05:27:45 Z zigui Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1603 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<30; 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);
                         ^
sterilizing.cpp: In member function 'void seg::move(int, int, int, int, int)':
sterilizing.cpp:99:29: warning: iteration 29u invokes undefined behavior [-Waggressive-loop-optimizations]
     tree[p][i] = tree[p][i+1];
                             ^
sterilizing.cpp:98:18: note: containing loop
    for(int i=0; i<30; i++){
                  ^

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 16 ms 66664 KB Output is correct
5 Correct 13 ms 66664 KB Output is correct
6 Correct 23 ms 66664 KB Output is correct
7 Correct 16 ms 66664 KB Output is correct
8 Correct 19 ms 66664 KB Output is correct
9 Correct 16 ms 66664 KB Output is correct
10 Correct 26 ms 66664 KB Output is correct
11 Correct 26 ms 66664 KB Output is correct
12 Correct 23 ms 66664 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 66664 KB Output is correct
2 Correct 66 ms 66664 KB Output is correct
3 Correct 49 ms 66664 KB Output is correct
4 Correct 66 ms 66664 KB Output is correct
5 Correct 73 ms 66664 KB Output is correct
6 Correct 86 ms 66664 KB Output is correct
7 Correct 79 ms 66664 KB Output is correct
8 Correct 99 ms 66664 KB Output is correct
9 Correct 96 ms 66664 KB Output is correct
10 Correct 73 ms 66664 KB Output is correct
11 Correct 76 ms 66664 KB Output is correct
12 Correct 86 ms 66664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 66664 KB Output is correct
2 Correct 299 ms 66664 KB Output is correct
3 Correct 403 ms 66664 KB Output is correct
4 Correct 686 ms 66664 KB Output is correct
5 Correct 1453 ms 66664 KB Output is correct
6 Correct 1303 ms 66664 KB Output is correct
7 Correct 66 ms 66664 KB Output is correct
8 Correct 1316 ms 66664 KB Output is correct
9 Correct 996 ms 66664 KB Output is correct
10 Correct 979 ms 66664 KB Output is correct
11 Correct 986 ms 66664 KB Output is correct
12 Correct 1079 ms 66664 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 66664 KB Output is correct
2 Correct 779 ms 66664 KB Output is correct
3 Correct 656 ms 66664 KB Output is correct
4 Correct 919 ms 66664 KB Output is correct
5 Correct 1413 ms 66664 KB Output is correct
6 Correct 1433 ms 66664 KB Output is correct
7 Correct 1473 ms 66664 KB Output is correct
8 Correct 1603 ms 66664 KB Output is correct
9 Correct 979 ms 66664 KB Output is correct
10 Correct 1066 ms 66664 KB Output is correct
11 Correct 939 ms 66664 KB Output is correct
12 Correct 1046 ms 66664 KB Output is correct