oj.uz

Submission #25517

# Submission time Handle Problem Language Result Execution time Memory
25517 2017-06-22T15:02:11 Z youngyojun Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 2166 ms 39468 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37844 KB Output is correct
2 Correct 0 ms 37844 KB Output is correct
3 Correct 6 ms 37844 KB Output is correct
4 Correct 16 ms 37844 KB Output is correct
5 Correct 19 ms 37988 KB Output is correct
6 Correct 9 ms 37844 KB Output is correct
7 Correct 13 ms 37988 KB Output is correct
8 Correct 16 ms 37988 KB Output is correct
9 Correct 23 ms 37988 KB Output is correct
10 Correct 13 ms 37984 KB Output is correct
11 Correct 16 ms 37988 KB Output is correct
12 Correct 16 ms 37984 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37844 KB Output is correct
2 Correct 16 ms 37844 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 26 ms 37844 KB Output is correct
5 Correct 29 ms 37844 KB Output is correct
6 Correct 29 ms 37844 KB Output is correct
7 Correct 29 ms 37844 KB Output is correct
8 Correct 36 ms 37844 KB Output is correct
9 Correct 33 ms 37844 KB Output is correct
10 Correct 33 ms 37844 KB Output is correct
11 Correct 29 ms 37844 KB Output is correct
12 Correct 36 ms 37844 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37844 KB Output is correct
2 Correct 23 ms 37984 KB Output is correct
3 Correct 19 ms 37984 KB Output is correct
4 Correct 46 ms 37988 KB Output is correct
5 Correct 63 ms 38116 KB Output is correct
6 Correct 63 ms 38116 KB Output is correct
7 Correct 29 ms 37844 KB Output is correct
8 Correct 59 ms 38312 KB Output is correct
9 Correct 56 ms 38696 KB Output is correct
10 Correct 59 ms 38700 KB Output is correct
11 Correct 56 ms 38696 KB Output is correct
12 Correct 79 ms 38696 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 38700 KB Output is correct
2 Correct 323 ms 38316 KB Output is correct
3 Correct 836 ms 38700 KB Output is correct
4 Correct 403 ms 38316 KB Output is correct
5 Correct 669 ms 38700 KB Output is correct
6 Correct 789 ms 38696 KB Output is correct
7 Correct 526 ms 39464 KB Output is correct
8 Correct 1179 ms 39464 KB Output is correct
9 Correct 1156 ms 39468 KB Output is correct
10 Correct 1336 ms 39468 KB Output is correct
11 Correct 676 ms 39464 KB Output is correct
12 Correct 2166 ms 39468 KB Output is correct