oj.uz

Submission #151974

# Submission time Handle Problem Language Result Execution time Memory
151974 2019-09-05T18:02:49 Z TadijaSebez Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 591 ms 9080 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
ll sum[N];
void Set(int i, ll f){ for(;i<N;i+=i&-i) sum[i]+=f;}
ll Get(int i){ ll ans=0;for(;i;i-=i&-i) ans+=sum[i];return ans;}
ll Get(int l, int r){ return Get(r)-Get(l-1);}
int a[N];
set<int> pos;
void upd(int x, int y){ Set(x,y-a[x]);a[x]=y;}
int main()
{
	int n,q,k;
	scanf("%i %i %i",&n,&q,&k);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),Set(i,a[i]),pos.insert(i);
	while(q--)
	{
		int t,l,r;
		scanf("%i %i %i",&t,&l,&r);
		if(t==1) upd(l,r),pos.insert(l);
		if(t==2 && k!=1)
		{
			for(auto it=pos.lower_bound(l);it!=pos.upper_bound(r);)
			{
				upd(*it,a[*it]/k);
				if(a[*it]==0) pos.erase(it++);
				else it++;
			}
		}
		if(t==3) printf("%lld\n",Get(l,r));
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&q,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:16:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),Set(i,a[i]),pos.insert(i);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&t,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 8 ms 632 KB Output is correct
8 Correct 8 ms 632 KB Output is correct
9 Correct 9 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 8 ms 632 KB Output is correct
12 Correct 8 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5672 KB Output is correct
2 Correct 70 ms 4392 KB Output is correct
3 Correct 79 ms 6776 KB Output is correct
4 Correct 105 ms 8644 KB Output is correct
5 Correct 116 ms 9080 KB Output is correct
6 Correct 118 ms 9080 KB Output is correct
7 Correct 121 ms 9080 KB Output is correct
8 Correct 121 ms 9068 KB Output is correct
9 Correct 114 ms 8956 KB Output is correct
10 Correct 113 ms 9028 KB Output is correct
11 Correct 113 ms 8924 KB Output is correct
12 Correct 114 ms 8924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1148 KB Output is correct
2 Correct 30 ms 3316 KB Output is correct
3 Correct 37 ms 3420 KB Output is correct
4 Correct 56 ms 3064 KB Output is correct
5 Correct 101 ms 7668 KB Output is correct
6 Correct 101 ms 7684 KB Output is correct
7 Correct 110 ms 7864 KB Output is correct
8 Correct 103 ms 7752 KB Output is correct
9 Correct 99 ms 7548 KB Output is correct
10 Correct 99 ms 7544 KB Output is correct
11 Correct 109 ms 7544 KB Output is correct
12 Correct 100 ms 7544 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 5240 KB Output is correct
2 Correct 120 ms 5248 KB Output is correct
3 Correct 176 ms 4216 KB Output is correct
4 Correct 132 ms 4132 KB Output is correct
5 Correct 213 ms 8904 KB Output is correct
6 Correct 246 ms 9052 KB Output is correct
7 Correct 209 ms 9044 KB Output is correct
8 Correct 326 ms 9080 KB Output is correct
9 Correct 351 ms 8772 KB Output is correct
10 Correct 390 ms 8824 KB Output is correct
11 Correct 273 ms 8796 KB Output is correct
12 Correct 591 ms 9004 KB Output is correct