Submission #25517

#	Time	Username	Problem	Language	Result	Execution time	Memory
25517		youngyojun	Sterilizing Spray (JOI15_sterilizing)	C++11	100 / 100	2166 ms	39468 KiB

sterilizing

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
#define MAXQ (100005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static unsigned char str[33355522], *p=str;
const int MX = 131072;
struct SEG {
	pii d[MX*2]; ll ds[MX*2];
	void upd(int x, int r) {
		for(d[x+MX] = {r, x}, x += MX, ds[x] = r, x /= 2; x; x /= 2) {
			d[x] = max(d[x*2], d[x*2+1]); ds[x] = ds[x*2] + ds[x*2+1];
		}
	}
	pii getmax(int s, int e) {
		pii r = {0, 0}; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) upmax(r, d[s++]); if(~e&1) upmax(r, d[e--]);
		} return r;
	}
	ll getsum(int s, int e) {
		ll r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) r += ds[s++]; if(~e&1) r += ds[e--];
		} return r;
	}
};

SEG seg;
vector<pii> V;
int N, Q, K;

int main() {
	fread(str, 1, 33355522, stdin);
	rf(N) rf(Q) rf(K)
	for(int i = 1, c; i <= N; i++) { rf(c) seg.upd(i, c); }
	for(int type, s, e; Q--;) {
		rf(type) rf(s) rf(e)
		if(1 == type) seg.upd(s, e);
		else if(2 == type) {
			if(1 == K) continue;
			for(pii r;;) {
				r = seg.getmax(s, e);
				if(!r.first) break;
				V.pb(r); seg.upd(r.second, 0);
			}
			for(pii v : V) seg.upd(v.second, v.first/K);
			clv(V);
		}
		else printf("%lld\n", seg.getsum(s, e));
	}
	return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:54:32: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 33355522, stdin);
                                ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75