oj.uz

Submission #69440

# Submission time Handle Problem Language Result Execution time Memory
69440 2018-08-20T21:07:12 Z thebes Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 311 ms 7332 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 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 3 ms 516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4576 KB Output is correct
2 Correct 21 ms 4576 KB Output is correct
3 Correct 25 ms 4576 KB Output is correct
4 Correct 49 ms 4576 KB Output is correct
5 Correct 74 ms 4576 KB Output is correct
6 Correct 91 ms 4624 KB Output is correct
7 Incorrect 112 ms 5612 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 99 ms 5612 KB Output is correct
2 Correct 105 ms 5612 KB Output is correct
3 Correct 141 ms 5612 KB Output is correct
4 Correct 133 ms 5612 KB Output is correct
5 Correct 199 ms 7288 KB Output is correct
6 Correct 209 ms 7332 KB Output is correct
7 Correct 171 ms 7332 KB Output is correct
8 Correct 244 ms 7332 KB Output is correct
9 Correct 236 ms 7332 KB Output is correct
10 Correct 311 ms 7332 KB Output is correct
11 Correct 171 ms 7332 KB Output is correct
12 Correct 295 ms 7332 KB Output is correct