oj.uz

Submission #25513

# Submission time Handle Problem Language Result Execution time Memory
25513 2017-06-22T14:57:56 Z youngyojun Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 1819 ms 7740 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 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;
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() {
	scanf("%d%d%d", &N, &Q, &K);
	for(int i = 1, c; i <= N; i++) { scanf("%d", &c); seg.upd(i, c); }
	for(int type, s, e; Q--;) {
		scanf("%d%d%d", &type, &s, &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:63: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:64:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1, c; i <= N; i++) { scanf("%d", &c); seg.upd(i, c); }
                                                  ^
sterilizing.cpp:66:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &type, &s, &e);
                                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6116 KB Output is correct
2 Correct 0 ms 6116 KB Output is correct
3 Correct 9 ms 6116 KB Output is correct
4 Correct 26 ms 6116 KB Output is correct
5 Correct 23 ms 6260 KB Output is correct
6 Correct 9 ms 6116 KB Output is correct
7 Correct 23 ms 6260 KB Output is correct
8 Correct 16 ms 6260 KB Output is correct
9 Correct 26 ms 6260 KB Output is correct
10 Correct 16 ms 6256 KB Output is correct
11 Correct 19 ms 6260 KB Output is correct
12 Correct 16 ms 6256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 6116 KB Output is correct
2 Correct 59 ms 6116 KB Output is correct
3 Correct 83 ms 6116 KB Output is correct
4 Correct 86 ms 6116 KB Output is correct
5 Correct 89 ms 6116 KB Output is correct
6 Correct 109 ms 6116 KB Output is correct
7 Correct 106 ms 6116 KB Output is correct
8 Correct 86 ms 6116 KB Output is correct
9 Correct 86 ms 6116 KB Output is correct
10 Correct 79 ms 6116 KB Output is correct
11 Correct 103 ms 6116 KB Output is correct
12 Correct 96 ms 6116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6116 KB Output is correct
2 Correct 29 ms 6256 KB Output is correct
3 Correct 56 ms 6256 KB Output is correct
4 Correct 83 ms 6260 KB Output is correct
5 Correct 126 ms 6388 KB Output is correct
6 Correct 126 ms 6388 KB Output is correct
7 Correct 79 ms 6116 KB Output is correct
8 Correct 109 ms 6584 KB Output is correct
9 Correct 143 ms 6968 KB Output is correct
10 Correct 93 ms 6972 KB Output is correct
11 Correct 116 ms 6968 KB Output is correct
12 Correct 113 ms 6968 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 6972 KB Output is correct
2 Correct 376 ms 6588 KB Output is correct
3 Correct 726 ms 6972 KB Output is correct
4 Correct 436 ms 6588 KB Output is correct
5 Correct 606 ms 6972 KB Output is correct
6 Correct 856 ms 6968 KB Output is correct
7 Correct 703 ms 7736 KB Output is correct
8 Correct 1176 ms 7736 KB Output is correct
9 Correct 1146 ms 7740 KB Output is correct
10 Correct 1183 ms 7740 KB Output is correct
11 Correct 813 ms 7736 KB Output is correct
12 Correct 1819 ms 7740 KB Output is correct