oj.uz

Submission #25511

# Submission time Handle Problem Language Result Execution time Memory
25511 2017-06-22T14:55:13 Z youngyojun Sterilizing Spray (JOI15_sterilizing) C++11
80 / 100
 5000 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) {
			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 3 ms 6116 KB Output is correct
2 Correct 26 ms 6116 KB Output is correct
3 Correct 6 ms 6116 KB Output is correct
4 Correct 23 ms 6116 KB Output is correct
5 Correct 16 ms 6260 KB Output is correct
6 Correct 9 ms 6116 KB Output is correct
7 Correct 16 ms 6260 KB Output is correct
8 Correct 19 ms 6260 KB Output is correct
9 Correct 23 ms 6260 KB Output is correct
10 Correct 16 ms 6256 KB Output is correct
11 Correct 16 ms 6260 KB Output is correct
12 Correct 19 ms 6256 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 6972 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6116 KB Output is correct
2 Correct 26 ms 6256 KB Output is correct
3 Correct 39 ms 6256 KB Output is correct
4 Correct 73 ms 6260 KB Output is correct
5 Correct 116 ms 6388 KB Output is correct
6 Correct 99 ms 6388 KB Output is correct
7 Execution timed out 5000 ms 6972 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 6972 KB Output is correct
2 Correct 336 ms 6588 KB Output is correct
3 Correct 756 ms 6972 KB Output is correct
4 Correct 469 ms 6588 KB Output is correct
5 Correct 696 ms 6972 KB Output is correct
6 Correct 823 ms 6968 KB Output is correct
7 Correct 606 ms 7736 KB Output is correct
8 Correct 1293 ms 7736 KB Output is correct
9 Correct 1126 ms 7740 KB Output is correct
10 Correct 1373 ms 7740 KB Output is correct
11 Correct 789 ms 7736 KB Output is correct
12 Correct 2199 ms 7740 KB Output is correct