oj.uz

Submission #223722

# Submission time Handle Problem Language Result Execution time Memory
223722 2020-04-16T08:10:22 Z cki86201 Sushi (JOI16_sushi) C++17
100 / 100
 6251 ms 125588 KB 
#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

const int BS = 400, MXN = 400040;
int N, Q, X[MXN];

struct Block {
	int V[BS+1], len;
	priority_queue <int> pq;
	priority_queue <int, vector<int>, greater<> > qs;
	void Init(int A[], int L) {
		for(int i=0;i<L;i++) {
			V[i] = A[i];
			pq.push(V[i]);
		}
		len = L;
	}
	int Push(int x) {
		qs.push(x);
		pq.push(x);
		int r = pq.top(); pq.pop();
		return r;
	}
	void Resolve() {
		rep(i, len) {
			qs.push(V[i]);
			V[i] = qs.top(); qs.pop();
		}
		while(!qs.empty()) qs.pop();
	}
	int query(int l, int r, int x) {
		if(l == 0 && r == len - 1) {
			return Push(x);
		}
		else {
			if(!qs.empty()) Resolve();
			for(int i=l;i<=r;i++) {
				if(V[i] > x) swap(V[i], x);
			}
			while(!pq.empty()) pq.pop();
			rep(i, len) pq.push(V[i]);
			return x;
		}
	}
} F[MXN/BS+3];

void Init() {
	for(int i=0;i*BS+1<=N;i++) {
		int lv = i * BS + 1, rv = min(N, (i+1) * BS);
		F[i].Init(X + lv, rv - lv + 1);
	}
}

int Query(int s, int t, int p) {
	if(s > t) {
		return Query(1, t, Query(s, N, p));
	}
	auto get_bn = [](int x) { return (x-1) / BS; };
	int sb = get_bn(s), st = get_bn(t);
	for(int i=sb;i<=st;i++) {
		int lv = i * BS + 1;
		int l = max(s, i*BS+1);
		int r = min(t, (i+1)*BS);
		p = F[i].query(l - lv, r - lv, p);
	}
	return p;
}

int main() {
	scanf("%d%d", &N, &Q);
	for(int i=1;i<=N;i++) scanf("%d", X + i);
	Init();
	for(int i=1;i<=Q;i++) {
		int s, t, p;
		scanf("%d%d%d", &s, &t, &p);
		printf("%d\n", Query(s, t, p));
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:82:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", X + i);
                        ~~~~~^~~~~~~~~~~~~
sushi.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &s, &t, &p);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 2048 KB Output is correct
2 Correct 124 ms 2048 KB Output is correct
3 Correct 127 ms 2128 KB Output is correct
4 Correct 128 ms 2120 KB Output is correct
5 Correct 126 ms 2048 KB Output is correct
6 Correct 127 ms 2048 KB Output is correct
7 Correct 58 ms 2048 KB Output is correct
8 Correct 59 ms 2048 KB Output is correct
9 Correct 127 ms 2048 KB Output is correct
10 Correct 124 ms 2168 KB Output is correct
11 Correct 122 ms 2168 KB Output is correct
12 Correct 127 ms 2168 KB Output is correct
13 Correct 129 ms 2048 KB Output is correct
14 Correct 132 ms 2048 KB Output is correct
15 Correct 133 ms 2048 KB Output is correct
16 Correct 62 ms 2048 KB Output is correct
17 Correct 5 ms 1920 KB Output is correct
18 Correct 5 ms 1920 KB Output is correct
19 Correct 5 ms 1920 KB Output is correct
20 Correct 5 ms 1920 KB Output is correct
21 Correct 5 ms 2048 KB Output is correct
22 Correct 5 ms 1920 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3420 ms 125248 KB Output is correct
2 Correct 3471 ms 123640 KB Output is correct
3 Correct 1745 ms 121720 KB Output is correct
4 Correct 3363 ms 125256 KB Output is correct
5 Correct 2749 ms 125344 KB Output is correct
6 Correct 3532 ms 125432 KB Output is correct
7 Correct 3531 ms 125452 KB Output is correct
8 Correct 3479 ms 125432 KB Output is correct
9 Correct 1580 ms 121848 KB Output is correct
10 Correct 2624 ms 123772 KB Output is correct
11 Correct 1578 ms 121848 KB Output is correct
12 Correct 2686 ms 123876 KB Output is correct
13 Correct 3340 ms 125292 KB Output is correct
14 Correct 3462 ms 123896 KB Output is correct
15 Correct 1736 ms 121888 KB Output is correct
16 Correct 3403 ms 125456 KB Output is correct
17 Correct 2774 ms 125284 KB Output is correct
18 Correct 3571 ms 125376 KB Output is correct
19 Correct 3507 ms 125432 KB Output is correct
20 Correct 3476 ms 125588 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 2048 KB Output is correct
2 Correct 124 ms 2048 KB Output is correct
3 Correct 127 ms 2128 KB Output is correct
4 Correct 128 ms 2120 KB Output is correct
5 Correct 126 ms 2048 KB Output is correct
6 Correct 127 ms 2048 KB Output is correct
7 Correct 58 ms 2048 KB Output is correct
8 Correct 59 ms 2048 KB Output is correct
9 Correct 127 ms 2048 KB Output is correct
10 Correct 124 ms 2168 KB Output is correct
11 Correct 122 ms 2168 KB Output is correct
12 Correct 127 ms 2168 KB Output is correct
13 Correct 129 ms 2048 KB Output is correct
14 Correct 132 ms 2048 KB Output is correct
15 Correct 133 ms 2048 KB Output is correct
16 Correct 62 ms 2048 KB Output is correct
17 Correct 5 ms 1920 KB Output is correct
18 Correct 5 ms 1920 KB Output is correct
19 Correct 5 ms 1920 KB Output is correct
20 Correct 5 ms 1920 KB Output is correct
21 Correct 5 ms 2048 KB Output is correct
22 Correct 5 ms 1920 KB Output is correct
23 Correct 3420 ms 125248 KB Output is correct
24 Correct 3471 ms 123640 KB Output is correct
25 Correct 1745 ms 121720 KB Output is correct
26 Correct 3363 ms 125256 KB Output is correct
27 Correct 2749 ms 125344 KB Output is correct
28 Correct 3532 ms 125432 KB Output is correct
29 Correct 3531 ms 125452 KB Output is correct
30 Correct 3479 ms 125432 KB Output is correct
31 Correct 1580 ms 121848 KB Output is correct
32 Correct 2624 ms 123772 KB Output is correct
33 Correct 1578 ms 121848 KB Output is correct
34 Correct 2686 ms 123876 KB Output is correct
35 Correct 3340 ms 125292 KB Output is correct
36 Correct 3462 ms 123896 KB Output is correct
37 Correct 1736 ms 121888 KB Output is correct
38 Correct 3403 ms 125456 KB Output is correct
39 Correct 2774 ms 125284 KB Output is correct
40 Correct 3571 ms 125376 KB Output is correct
41 Correct 3507 ms 125432 KB Output is correct
42 Correct 3476 ms 125588 KB Output is correct
43 Correct 4083 ms 17928 KB Output is correct
44 Correct 4051 ms 17452 KB Output is correct
45 Correct 2235 ms 14084 KB Output is correct
46 Correct 4074 ms 17756 KB Output is correct
47 Correct 4017 ms 17784 KB Output is correct
48 Correct 4441 ms 17856 KB Output is correct
49 Correct 4640 ms 17748 KB Output is correct
50 Correct 4645 ms 17676 KB Output is correct
51 Correct 4631 ms 17912 KB Output is correct
52 Correct 5889 ms 31468 KB Output is correct
53 Correct 5778 ms 29736 KB Output is correct
54 Correct 5969 ms 29804 KB Output is correct
55 Correct 6251 ms 30132 KB Output is correct
56 Correct 6228 ms 30072 KB Output is correct
57 Correct 6196 ms 30184 KB Output is correct
58 Correct 3445 ms 21288 KB Output is correct
59 Correct 3455 ms 21196 KB Output is correct
60 Correct 3822 ms 125304 KB Output is correct
61 Correct 4859 ms 124908 KB Output is correct
62 Correct 4853 ms 125028 KB Output is correct
63 Correct 4796 ms 124920 KB Output is correct
64 Correct 1621 ms 14200 KB Output is correct
65 Correct 2301 ms 67340 KB Output is correct
66 Correct 2260 ms 67320 KB Output is correct
67 Correct 4406 ms 103036 KB Output is correct
68 Correct 5113 ms 103164 KB Output is correct
69 Correct 5105 ms 103160 KB Output is correct
70 Correct 5037 ms 102996 KB Output is correct