oj.uz

Submission #50338

# Submission time Handle Problem Language Result Execution time Memory
50338 2018-06-10T08:49:16 Z gnoor Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 185 ms 7104 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;
		add(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]);
				tbl[b]=c;
			} 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:43: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 5 ms 572 KB Output is correct
5 Correct 5 ms 628 KB Output is correct
6 Correct 5 ms 756 KB Output is correct
7 Correct 5 ms 756 KB Output is correct
8 Correct 5 ms 916 KB Output is correct
9 Correct 6 ms 916 KB Output is correct
10 Correct 6 ms 916 KB Output is correct
11 Correct 5 ms 916 KB Output is correct
12 Correct 5 ms 916 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 3900 KB Output is correct
2 Correct 53 ms 3900 KB Output is correct
3 Correct 65 ms 5580 KB Output is correct
4 Correct 92 ms 6724 KB Output is correct
5 Correct 96 ms 7104 KB Output is correct
6 Correct 94 ms 7104 KB Output is correct
7 Correct 93 ms 7104 KB Output is correct
8 Correct 98 ms 7104 KB Output is correct
9 Correct 91 ms 7104 KB Output is correct
10 Correct 95 ms 7104 KB Output is correct
11 Correct 97 ms 7104 KB Output is correct
12 Correct 91 ms 7104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7104 KB Output is correct
2 Correct 33 ms 7104 KB Output is correct
3 Correct 35 ms 7104 KB Output is correct
4 Correct 46 ms 7104 KB Output is correct
5 Correct 91 ms 7104 KB Output is correct
6 Correct 88 ms 7104 KB Output is correct
7 Correct 80 ms 7104 KB Output is correct
8 Correct 85 ms 7104 KB Output is correct
9 Correct 93 ms 7104 KB Output is correct
10 Correct 91 ms 7104 KB Output is correct
11 Correct 84 ms 7104 KB Output is correct
12 Correct 78 ms 7104 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 7104 KB Output is correct
2 Correct 87 ms 7104 KB Output is correct
3 Correct 88 ms 7104 KB Output is correct
4 Correct 88 ms 7104 KB Output is correct
5 Correct 141 ms 7104 KB Output is correct
6 Correct 147 ms 7104 KB Output is correct
7 Correct 155 ms 7104 KB Output is correct
8 Correct 160 ms 7104 KB Output is correct
9 Correct 171 ms 7104 KB Output is correct
10 Correct 144 ms 7104 KB Output is correct
11 Correct 123 ms 7104 KB Output is correct
12 Correct 185 ms 7104 KB Output is correct