oj.uz

Submission #25514

# Submission time Handle Problem Language Result Execution time Memory
25514 2017-06-22T14:59:56 Z youngyojun Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 1976 ms 61992 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#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[55555555], *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, 55555555, 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:65: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, 55555555, stdin);
                                ^

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 60368 KB Output is correct
2 Correct 16 ms 60508 KB Output is correct
3 Correct 26 ms 60508 KB Output is correct
4 Correct 49 ms 60512 KB Output is correct
5 Correct 69 ms 60640 KB Output is correct
6 Correct 73 ms 60640 KB Output is correct
7 Correct 46 ms 60368 KB Output is correct
8 Correct 73 ms 60836 KB Output is correct
9 Correct 66 ms 61220 KB Output is correct
10 Correct 63 ms 61224 KB Output is correct
11 Correct 79 ms 61220 KB Output is correct
12 Correct 56 ms 61220 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 61224 KB Output is correct
2 Correct 296 ms 60840 KB Output is correct
3 Correct 753 ms 61224 KB Output is correct
4 Correct 443 ms 60840 KB Output is correct
5 Correct 619 ms 61224 KB Output is correct
6 Correct 789 ms 61220 KB Output is correct
7 Correct 619 ms 61988 KB Output is correct
8 Correct 1079 ms 61988 KB Output is correct
9 Correct 1066 ms 61992 KB Output is correct
10 Correct 1156 ms 61992 KB Output is correct
11 Correct 766 ms 61988 KB Output is correct
12 Correct 1976 ms 61992 KB Output is correct