oj.uz

Submission #69441

# Submission time Handle Problem Language Result Execution time Memory
69441 2018-08-20T21:08:06 Z thebes Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 339 ms 38904 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e5+5;
typedef long long ll;
ll bit[MN], arr[MN], N, M, K, i, x, y;
set<ll> s;

void upd(ll p,ll d){for(;p<=N;p+=p&-p)bit[p]+=d;}
ll qu(ll p){ll s=0;for(;p;p-=p&-p)s+=bit[p]; return s;}

int main(){
	scanf("%lld%lld%lld",&N,&M,&K);
	for(i=1;i<=N;i++){
		scanf("%lld",&arr[i]);
		upd(i, arr[i]);
		if(arr[i]) s.insert(i);
	}
	for(;M;M--){
		scanf("%lld%lld%lld",&i,&x,&y);
		if(i==1){
			upd(x, y-arr[x]); arr[x] = y;
			s.insert(x);
		}
		else if(i==2&&K!=1){
			auto it = s.lower_bound(x);
			for(;it!=s.end()&&*it<=y;){
				upd(*it,(arr[*it]/K)-arr[*it]);
				arr[*it]=arr[*it]/K;
				if(!arr[*it]){
					auto it2 = it; it++;
					s.erase(it2);
				}
				else it++;
			}
		}
		else if(i==3) printf("%lld\n",qu(y)-qu(x-1));
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&i,&x,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 4 ms 580 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 9 ms 940 KB Output is correct
6 Correct 6 ms 1004 KB Output is correct
7 Correct 7 ms 1072 KB Output is correct
8 Correct 8 ms 1140 KB Output is correct
9 Correct 9 ms 1208 KB Output is correct
10 Correct 8 ms 1292 KB Output is correct
11 Correct 7 ms 1364 KB Output is correct
12 Correct 7 ms 1428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4684 KB Output is correct
2 Correct 75 ms 5392 KB Output is correct
3 Correct 83 ms 9748 KB Output is correct
4 Correct 123 ms 13272 KB Output is correct
5 Correct 153 ms 16044 KB Output is correct
6 Correct 125 ms 18312 KB Output is correct
7 Correct 136 ms 21024 KB Output is correct
8 Correct 120 ms 23252 KB Output is correct
9 Correct 135 ms 25576 KB Output is correct
10 Correct 140 ms 27892 KB Output is correct
11 Correct 128 ms 30196 KB Output is correct
12 Correct 127 ms 32644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 32644 KB Output is correct
2 Correct 21 ms 32644 KB Output is correct
3 Correct 26 ms 32644 KB Output is correct
4 Correct 50 ms 32644 KB Output is correct
5 Correct 77 ms 32644 KB Output is correct
6 Correct 86 ms 32644 KB Output is correct
7 Correct 103 ms 32644 KB Output is correct
8 Correct 126 ms 32644 KB Output is correct
9 Correct 70 ms 32644 KB Output is correct
10 Correct 77 ms 33908 KB Output is correct
11 Correct 71 ms 35032 KB Output is correct
12 Correct 115 ms 36208 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 36208 KB Output is correct
2 Correct 107 ms 36208 KB Output is correct
3 Correct 156 ms 36208 KB Output is correct
4 Correct 109 ms 36208 KB Output is correct
5 Correct 189 ms 38868 KB Output is correct
6 Correct 228 ms 38888 KB Output is correct
7 Correct 199 ms 38888 KB Output is correct
8 Correct 236 ms 38904 KB Output is correct
9 Correct 229 ms 38904 KB Output is correct
10 Correct 242 ms 38904 KB Output is correct
11 Correct 201 ms 38904 KB Output is correct
12 Correct 339 ms 38904 KB Output is correct