Submission #25051

#	Time	Username	Problem	Language	Result	Execution time	Memory
25051		zigui	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	2073 ms	8244 KiB

sterilizing

#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;

const int MX = 1<<17;
const int MM = 1000000007;

struct Tree{
	pii t[MX*2];
	ll tot[MX*2];
	ll sum(int s, int e){
		s += MX, e += MX;
		ll r = 0;
		while( s <= e){
			if( s&1 ) r += tot[s++];
			if(~e&1 ) r += tot[e--];
			s /= 2, e /= 2;
		}
		return r;
	}
	pii read(int s, int e){
		s += MX, e += MX;
		pii mx = pii(0, -1);
		while( s <= e){
			if( s&1 ) mx = max(mx, t[s++]);
			if(~e&1 ) mx = max(mx, t[e--]);
			s /= 2, e /= 2;
		}
		return mx;
	}
	void update(int x, int v){
		x += MX; t[x] = pii(v, x-MX); tot[x] = v;
		while(x > 1){
			x /= 2; t[x] = max(t[x*2], t[x*2+1]);
			tot[x] = tot[x*2] + tot[x*2+1];
		}
	}
} tree;

int a, b, c, d;
int main()
{
	int N, Q, K;
	scanf("%d%d%d", &N, &Q, &K);
	for(int i = 1; i <= N; i++){
		scanf("%d", &a);
		tree.update(i, a);
	}
	for(int i = 1; i <= Q; i++){
		scanf("%d%d%d", &a, &b, &c);
		if( a == 1 ){
			tree.update(b, c);
		}
		else if( a == 2 ){
			if( K != 1 ){
				vector<pii> L;
				while(1){
					pii mx = tree.read(b, c);
					if( mx.first == 0 ) break;
					tree.update(mx.second, 0);
					L.emplace_back(mx.second, mx.first / K);
				}
				for(pii c : L) tree.update(c.first, c.second);
			}
		}
		else{
			printf("%lld\n", tree.sum(b, c));
		}
	}
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:64:29: 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:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^
sterilizing.cpp:70:30: 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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75