# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
699882 |
2023-02-18T07:50:59 Z |
bdl |
Sushi (JOI16_sushi) |
C++17 |
|
2172 ms |
51984 KB |
/*
> Statement
You are given a circular array A of length N. You are given Q queries, each giving (l, r, a). You are to run the following code:
for (int i = l; i <= r; i++)
if (a < A[i])
swap(a, A[i]);
For each query, output the final value of a.
> Scoring
05: 1 <= N, Q <= 2e3
15: For all queries, l = r = 1
80: 1 <= N <= 4e5, 1 <= Q <= 2.5e4, 1 <= A_i <= 1e9
*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 4e5, B = 1000;
char _buf[1 << 20], *_p1, *_p2;
#define getchar() (_p1 == _p2 ? (_p2 = _buf + fread(_p1 = _buf, 1, 1 << 20, stdin), _p1 == _p2 ? EOF : *_p1++) : *_p1++)
int read() {
int s = 0, w = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
w = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return s * w;
}
struct T {
int *a, n;
vector<int> u;
priority_queue<int> v;
void build(int *a_, int n_) {
a = a_, n = n_;
pull();
}
void pull() {
v = priority_queue<int>(a, a + n);
}
int force(int l, int r, int x) {
for (int i = l; i <= r; i++)
if (x < a[i])
swap(x, a[i]);
return x;
}
int put(int x) {
int t = v.top();
if (x < t) {
v.pop();
v.push(x);
u.push_back(x);
x = t;
}
return x;
}
void push() {
if (u.empty())
return;
static priority_queue<int, vector<int>, greater<int>> u_;
u_ = priority_queue<int, vector<int>, greater<int>>(u.begin(), u.end());
int t = u_.top();
for (int i = 0; i < n; i++)
if (t < a[i]) {
u_.pop(), u_.push(a[i]);
a[i] = t, t = u_.top();
}
u.clear();
}
} b[(N - 1) / B + 1];
int main() {
int n = read(), q = read();
static int a[N];
for (int i = 0; i < n; i++)
a[i] = read();
for (int i = 0; i <= (n - 1) / B; i++)
b[i].build(a + B * i, min(n, B * (i + 1)) - B * i);
while (q--) {
int l = read() - 1, r = read() - 1, x = read();
if (l <= r) {
if (l / B == r / B) {
b[l / B].push();
x = b[l / B].force(l - l / B * B, r - l / B * B, x);
b[l / B].pull();
} else {
b[l / B].push();
x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x);
b[l / B].pull();
for (int i = l / B + 1; i < r / B; i++)
x = b[i].put(x);
b[r / B].push();
x = b[r / B].force(0, r - r / B * B, x);
b[r / B].pull();
}
} else {
if (l / B == r / B) {
b[l / B].push();
x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x);
for (int i = l / B + 1; i <= (n - 1) / B; i++)
x = b[i].put(x);
for (int i = 0; i < l / B; i++)
x = b[i].put(x);
x = b[l / B].force(0, r - l / B * B, x);
b[l / B].pull();
} else {
b[l / B].push();
x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x);
b[l / B].pull();
for (int i = l / B + 1; i <= (n - 1) / B; i++)
x = b[i].put(x);
for (int i = 0; i < r / B; i++)
x = b[i].put(x);
b[r / B].push();
x = b[r / B].force(0, r - r / B * B, x);
b[r / B].pull();
}
}
printf("%d\n", x);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
340 KB |
Output is correct |
2 |
Correct |
24 ms |
424 KB |
Output is correct |
3 |
Correct |
22 ms |
432 KB |
Output is correct |
4 |
Correct |
25 ms |
340 KB |
Output is correct |
5 |
Correct |
22 ms |
408 KB |
Output is correct |
6 |
Correct |
24 ms |
340 KB |
Output is correct |
7 |
Correct |
16 ms |
340 KB |
Output is correct |
8 |
Correct |
17 ms |
340 KB |
Output is correct |
9 |
Correct |
22 ms |
428 KB |
Output is correct |
10 |
Correct |
24 ms |
436 KB |
Output is correct |
11 |
Correct |
23 ms |
340 KB |
Output is correct |
12 |
Correct |
24 ms |
428 KB |
Output is correct |
13 |
Correct |
24 ms |
444 KB |
Output is correct |
14 |
Correct |
19 ms |
340 KB |
Output is correct |
15 |
Correct |
19 ms |
340 KB |
Output is correct |
16 |
Correct |
15 ms |
436 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1074 ms |
51028 KB |
Output is correct |
2 |
Correct |
1105 ms |
51432 KB |
Output is correct |
3 |
Correct |
248 ms |
4668 KB |
Output is correct |
4 |
Correct |
1122 ms |
51488 KB |
Output is correct |
5 |
Correct |
657 ms |
50760 KB |
Output is correct |
6 |
Correct |
983 ms |
50684 KB |
Output is correct |
7 |
Correct |
924 ms |
50668 KB |
Output is correct |
8 |
Correct |
933 ms |
50716 KB |
Output is correct |
9 |
Correct |
231 ms |
4628 KB |
Output is correct |
10 |
Correct |
656 ms |
48100 KB |
Output is correct |
11 |
Correct |
214 ms |
4500 KB |
Output is correct |
12 |
Correct |
636 ms |
48684 KB |
Output is correct |
13 |
Correct |
1066 ms |
51272 KB |
Output is correct |
14 |
Correct |
1079 ms |
51652 KB |
Output is correct |
15 |
Correct |
263 ms |
4556 KB |
Output is correct |
16 |
Correct |
1052 ms |
51984 KB |
Output is correct |
17 |
Correct |
669 ms |
50704 KB |
Output is correct |
18 |
Correct |
927 ms |
50832 KB |
Output is correct |
19 |
Correct |
931 ms |
50732 KB |
Output is correct |
20 |
Correct |
989 ms |
50700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
340 KB |
Output is correct |
2 |
Correct |
24 ms |
424 KB |
Output is correct |
3 |
Correct |
22 ms |
432 KB |
Output is correct |
4 |
Correct |
25 ms |
340 KB |
Output is correct |
5 |
Correct |
22 ms |
408 KB |
Output is correct |
6 |
Correct |
24 ms |
340 KB |
Output is correct |
7 |
Correct |
16 ms |
340 KB |
Output is correct |
8 |
Correct |
17 ms |
340 KB |
Output is correct |
9 |
Correct |
22 ms |
428 KB |
Output is correct |
10 |
Correct |
24 ms |
436 KB |
Output is correct |
11 |
Correct |
23 ms |
340 KB |
Output is correct |
12 |
Correct |
24 ms |
428 KB |
Output is correct |
13 |
Correct |
24 ms |
444 KB |
Output is correct |
14 |
Correct |
19 ms |
340 KB |
Output is correct |
15 |
Correct |
19 ms |
340 KB |
Output is correct |
16 |
Correct |
15 ms |
436 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
288 KB |
Output is correct |
23 |
Correct |
1074 ms |
51028 KB |
Output is correct |
24 |
Correct |
1105 ms |
51432 KB |
Output is correct |
25 |
Correct |
248 ms |
4668 KB |
Output is correct |
26 |
Correct |
1122 ms |
51488 KB |
Output is correct |
27 |
Correct |
657 ms |
50760 KB |
Output is correct |
28 |
Correct |
983 ms |
50684 KB |
Output is correct |
29 |
Correct |
924 ms |
50668 KB |
Output is correct |
30 |
Correct |
933 ms |
50716 KB |
Output is correct |
31 |
Correct |
231 ms |
4628 KB |
Output is correct |
32 |
Correct |
656 ms |
48100 KB |
Output is correct |
33 |
Correct |
214 ms |
4500 KB |
Output is correct |
34 |
Correct |
636 ms |
48684 KB |
Output is correct |
35 |
Correct |
1066 ms |
51272 KB |
Output is correct |
36 |
Correct |
1079 ms |
51652 KB |
Output is correct |
37 |
Correct |
263 ms |
4556 KB |
Output is correct |
38 |
Correct |
1052 ms |
51984 KB |
Output is correct |
39 |
Correct |
669 ms |
50704 KB |
Output is correct |
40 |
Correct |
927 ms |
50832 KB |
Output is correct |
41 |
Correct |
931 ms |
50732 KB |
Output is correct |
42 |
Correct |
989 ms |
50700 KB |
Output is correct |
43 |
Correct |
693 ms |
5108 KB |
Output is correct |
44 |
Correct |
719 ms |
5224 KB |
Output is correct |
45 |
Correct |
351 ms |
4520 KB |
Output is correct |
46 |
Correct |
697 ms |
5088 KB |
Output is correct |
47 |
Correct |
707 ms |
5144 KB |
Output is correct |
48 |
Correct |
2019 ms |
5960 KB |
Output is correct |
49 |
Correct |
2157 ms |
5976 KB |
Output is correct |
50 |
Correct |
2172 ms |
6168 KB |
Output is correct |
51 |
Correct |
2120 ms |
6164 KB |
Output is correct |
52 |
Correct |
419 ms |
5636 KB |
Output is correct |
53 |
Correct |
437 ms |
5488 KB |
Output is correct |
54 |
Correct |
1546 ms |
7040 KB |
Output is correct |
55 |
Correct |
1587 ms |
7084 KB |
Output is correct |
56 |
Correct |
1581 ms |
7108 KB |
Output is correct |
57 |
Correct |
1549 ms |
6988 KB |
Output is correct |
58 |
Correct |
1691 ms |
7228 KB |
Output is correct |
59 |
Correct |
1650 ms |
7152 KB |
Output is correct |
60 |
Correct |
644 ms |
50584 KB |
Output is correct |
61 |
Correct |
922 ms |
50684 KB |
Output is correct |
62 |
Correct |
942 ms |
50608 KB |
Output is correct |
63 |
Correct |
874 ms |
50620 KB |
Output is correct |
64 |
Correct |
234 ms |
4520 KB |
Output is correct |
65 |
Correct |
393 ms |
27140 KB |
Output is correct |
66 |
Correct |
451 ms |
27340 KB |
Output is correct |
67 |
Correct |
335 ms |
29884 KB |
Output is correct |
68 |
Correct |
522 ms |
29924 KB |
Output is correct |
69 |
Correct |
477 ms |
29884 KB |
Output is correct |
70 |
Correct |
501 ms |
29888 KB |
Output is correct |