oj.uz

Submission #50336

# Submission time Handle Problem Language Result Execution time Memory
50336 2018-06-10T08:41:50 Z gnoor Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 206 ms 6488 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

map<int,int> st;

long long bit[100100];

void add(int idx,int val) {
	while (idx<100100) {
		bit[idx]+=val;
		idx+=(idx&-idx);
	}
}

long long get(int idx) {
	long long sum=0;
	while (idx) {
		sum+=bit[idx];
		idx-=(idx&-idx);
	}
	return sum;
}

int tbl[100100];

int main () {
	int n,q,k;
	scanf("%d%d%d",&n,&q,&k);
	int x;
	for (int i=1;i<=n;i++) {
		scanf("%d",&x);
		tbl[i]=x;
		//st.insert(make_pair(i,x));
		st[i]=x;
	}
	int a,b,c;
	for (int i=0;i<q;i++) {
		scanf("%d%d%d",&a,&b,&c);
		if (k==1) {
			if (a==1) {
				add(b,c-tbl[b]);
			} else if (a==3) {
				printf("%lld\n",get(c)-get(b-1));
			}	
			continue;
		}
		if (a==1) {
			//auto &now = st.lower_bound(make_pair(b,-1));
			if (c==0) {
				st.erase(b);
			} else {
				st[b]=c;
			}
		} else if (a==2) {
			//if (k==1) continue;
			auto xx=st.lower_bound(b);
			for(;xx->first<=c&&xx!=st.end();) {
				xx->second/=k;
				if (xx->second==0) {
					auto tmp=xx;
					xx++;
					st.erase(tmp);
				} else {
					xx++;
				}
			}
		} else if (a==3) {
			auto xx=st.lower_bound(b);
			long long ans=0;
			for (;xx->first<=c&&xx!=st.end();xx++) {
				ans+=xx->second;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:32:7: 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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
sterilizing.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3612 KB Output is correct
2 Correct 28 ms 3612 KB Output is correct
3 Correct 28 ms 3612 KB Output is correct
4 Correct 53 ms 3612 KB Output is correct
5 Correct 82 ms 5692 KB Output is correct
6 Correct 85 ms 5712 KB Output is correct
7 Incorrect 80 ms 6488 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 90 ms 6488 KB Output is correct
2 Correct 94 ms 6488 KB Output is correct
3 Correct 95 ms 6488 KB Output is correct
4 Correct 86 ms 6488 KB Output is correct
5 Correct 129 ms 6488 KB Output is correct
6 Correct 145 ms 6488 KB Output is correct
7 Correct 128 ms 6488 KB Output is correct
8 Correct 157 ms 6488 KB Output is correct
9 Correct 206 ms 6488 KB Output is correct
10 Correct 161 ms 6488 KB Output is correct
11 Correct 119 ms 6488 KB Output is correct
12 Correct 178 ms 6488 KB Output is correct