oj.uz

Submission #69435

# Submission time Handle Problem Language Result Execution time Memory
69435 2018-08-20T20:40:46 Z thebes Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 367 ms 41180 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){
			if(s.count(x)) s.erase(s.find(x));
			upd(x, y-arr[x]); arr[x] = y;
			if(arr[x]) 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 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Incorrect 4 ms 660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 6384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6384 KB Output is correct
2 Correct 21 ms 6384 KB Output is correct
3 Correct 30 ms 6384 KB Output is correct
4 Correct 51 ms 6384 KB Output is correct
5 Correct 84 ms 10512 KB Output is correct
6 Correct 93 ms 12020 KB Output is correct
7 Incorrect 106 ms 13704 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 14460 KB Output is correct
2 Correct 115 ms 16136 KB Output is correct
3 Correct 146 ms 16872 KB Output is correct
4 Correct 125 ms 17980 KB Output is correct
5 Correct 214 ms 24684 KB Output is correct
6 Correct 224 ms 27088 KB Output is correct
7 Correct 197 ms 29628 KB Output is correct
8 Correct 308 ms 32096 KB Output is correct
9 Correct 212 ms 34304 KB Output is correct
10 Correct 252 ms 36732 KB Output is correct
11 Correct 211 ms 38912 KB Output is correct
12 Correct 367 ms 41180 KB Output is correct