# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
56108 | 2018-07-10T04:16:19 Z | 테스트2(#2107) | Sushi (JOI16_sushi) | C++11 | 7033 ms | 70776 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; const int t = 700; int n, q, g; int v[400000]; priority_queue<int> mx[t]; priority_queue<int, vector<int>, greater<int>> pass[t]; void reconstruct(int x) { for (int i = x * t; i < (x + 1) * t && i < n; ++i) { pass[x].push(v[i]); v[i] = pass[x].top(); pass[x].pop(); } while (!pass[x].empty()) pass[x].pop(); } void construct(int x) { while (!mx[x].empty()) mx[x].pop(); for (int i = x * t; i < (x + 1) * t && i < n; ++i) { mx[x].push(v[i]); } } int main() { scanf("%d%d", &n, &q); for (int i = 0; i < n; ++i) { scanf("%d", v + i); } g = (n - 1) / t + 1; for (int i = 0; i < t; ++i) { for (int j = i * t; j < (i + 1) * t && j < n; ++j) { mx[i].push(v[j]); } } while (q--) { int s, e, p; scanf("%d%d%d", &s, &e, &p); --s; --e; int sg = s / t; int eg = e / t; reconstruct(sg); if (sg != eg) reconstruct(eg); if (sg == eg && s <= e) { for (int i = s; i <= e; ++i) { if (p < v[i]) swap(p, v[i]); } } else { for (int i = s; i < (sg + 1) * t && i < n; ++i) { if (p < v[i]) swap(p, v[i]); } for (int i = (sg + 1) % g; i != eg; i = (i + 1) % g) { pass[i].push(p); mx[i].push(p); p = mx[i].top(); mx[i].pop(); } for (int i = eg * t; i <= e; ++i) { if (p < v[i]) swap(p, v[i]); } } construct(sg); if (sg != eg) construct(eg); printf("%d\n", p); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 230 ms | 408 KB | Output is correct |
2 | Correct | 268 ms | 740 KB | Output is correct |
3 | Correct | 267 ms | 740 KB | Output is correct |
4 | Correct | 245 ms | 740 KB | Output is correct |
5 | Correct | 278 ms | 740 KB | Output is correct |
6 | Correct | 234 ms | 744 KB | Output is correct |
7 | Correct | 115 ms | 744 KB | Output is correct |
8 | Correct | 97 ms | 744 KB | Output is correct |
9 | Correct | 227 ms | 744 KB | Output is correct |
10 | Correct | 206 ms | 744 KB | Output is correct |
11 | Correct | 207 ms | 752 KB | Output is correct |
12 | Correct | 208 ms | 752 KB | Output is correct |
13 | Correct | 216 ms | 752 KB | Output is correct |
14 | Correct | 152 ms | 752 KB | Output is correct |
15 | Correct | 153 ms | 752 KB | Output is correct |
16 | Correct | 131 ms | 752 KB | Output is correct |
17 | Correct | 3 ms | 752 KB | Output is correct |
18 | Correct | 3 ms | 752 KB | Output is correct |
19 | Correct | 2 ms | 752 KB | Output is correct |
20 | Correct | 2 ms | 752 KB | Output is correct |
21 | Correct | 3 ms | 752 KB | Output is correct |
22 | Correct | 3 ms | 752 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5474 ms | 70520 KB | Output is correct |
2 | Correct | 5886 ms | 70520 KB | Output is correct |
3 | Correct | 2662 ms | 70520 KB | Output is correct |
4 | Correct | 5819 ms | 70520 KB | Output is correct |
5 | Correct | 4657 ms | 70624 KB | Output is correct |
6 | Correct | 5742 ms | 70624 KB | Output is correct |
7 | Correct | 5687 ms | 70624 KB | Output is correct |
8 | Correct | 5838 ms | 70624 KB | Output is correct |
9 | Correct | 1994 ms | 70624 KB | Output is correct |
10 | Correct | 4772 ms | 70624 KB | Output is correct |
11 | Correct | 2247 ms | 70624 KB | Output is correct |
12 | Correct | 4923 ms | 70624 KB | Output is correct |
13 | Correct | 6324 ms | 70624 KB | Output is correct |
14 | Correct | 5493 ms | 70624 KB | Output is correct |
15 | Correct | 2478 ms | 70624 KB | Output is correct |
16 | Correct | 6035 ms | 70624 KB | Output is correct |
17 | Correct | 5027 ms | 70624 KB | Output is correct |
18 | Correct | 5492 ms | 70668 KB | Output is correct |
19 | Correct | 5853 ms | 70668 KB | Output is correct |
20 | Correct | 5823 ms | 70668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 230 ms | 408 KB | Output is correct |
2 | Correct | 268 ms | 740 KB | Output is correct |
3 | Correct | 267 ms | 740 KB | Output is correct |
4 | Correct | 245 ms | 740 KB | Output is correct |
5 | Correct | 278 ms | 740 KB | Output is correct |
6 | Correct | 234 ms | 744 KB | Output is correct |
7 | Correct | 115 ms | 744 KB | Output is correct |
8 | Correct | 97 ms | 744 KB | Output is correct |
9 | Correct | 227 ms | 744 KB | Output is correct |
10 | Correct | 206 ms | 744 KB | Output is correct |
11 | Correct | 207 ms | 752 KB | Output is correct |
12 | Correct | 208 ms | 752 KB | Output is correct |
13 | Correct | 216 ms | 752 KB | Output is correct |
14 | Correct | 152 ms | 752 KB | Output is correct |
15 | Correct | 153 ms | 752 KB | Output is correct |
16 | Correct | 131 ms | 752 KB | Output is correct |
17 | Correct | 3 ms | 752 KB | Output is correct |
18 | Correct | 3 ms | 752 KB | Output is correct |
19 | Correct | 2 ms | 752 KB | Output is correct |
20 | Correct | 2 ms | 752 KB | Output is correct |
21 | Correct | 3 ms | 752 KB | Output is correct |
22 | Correct | 3 ms | 752 KB | Output is correct |
23 | Correct | 5474 ms | 70520 KB | Output is correct |
24 | Correct | 5886 ms | 70520 KB | Output is correct |
25 | Correct | 2662 ms | 70520 KB | Output is correct |
26 | Correct | 5819 ms | 70520 KB | Output is correct |
27 | Correct | 4657 ms | 70624 KB | Output is correct |
28 | Correct | 5742 ms | 70624 KB | Output is correct |
29 | Correct | 5687 ms | 70624 KB | Output is correct |
30 | Correct | 5838 ms | 70624 KB | Output is correct |
31 | Correct | 1994 ms | 70624 KB | Output is correct |
32 | Correct | 4772 ms | 70624 KB | Output is correct |
33 | Correct | 2247 ms | 70624 KB | Output is correct |
34 | Correct | 4923 ms | 70624 KB | Output is correct |
35 | Correct | 6324 ms | 70624 KB | Output is correct |
36 | Correct | 5493 ms | 70624 KB | Output is correct |
37 | Correct | 2478 ms | 70624 KB | Output is correct |
38 | Correct | 6035 ms | 70624 KB | Output is correct |
39 | Correct | 5027 ms | 70624 KB | Output is correct |
40 | Correct | 5492 ms | 70668 KB | Output is correct |
41 | Correct | 5853 ms | 70668 KB | Output is correct |
42 | Correct | 5823 ms | 70668 KB | Output is correct |
43 | Correct | 5758 ms | 70668 KB | Output is correct |
44 | Correct | 6037 ms | 70668 KB | Output is correct |
45 | Correct | 4144 ms | 70668 KB | Output is correct |
46 | Correct | 5968 ms | 70668 KB | Output is correct |
47 | Correct | 5574 ms | 70668 KB | Output is correct |
48 | Correct | 6119 ms | 70668 KB | Output is correct |
49 | Correct | 7033 ms | 70668 KB | Output is correct |
50 | Correct | 6632 ms | 70668 KB | Output is correct |
51 | Correct | 6483 ms | 70668 KB | Output is correct |
52 | Correct | 5514 ms | 70668 KB | Output is correct |
53 | Correct | 5491 ms | 70668 KB | Output is correct |
54 | Correct | 6049 ms | 70668 KB | Output is correct |
55 | Correct | 6131 ms | 70668 KB | Output is correct |
56 | Correct | 5951 ms | 70668 KB | Output is correct |
57 | Correct | 6345 ms | 70668 KB | Output is correct |
58 | Correct | 5952 ms | 70668 KB | Output is correct |
59 | Correct | 5316 ms | 70668 KB | Output is correct |
60 | Correct | 5324 ms | 70668 KB | Output is correct |
61 | Correct | 5795 ms | 70668 KB | Output is correct |
62 | Correct | 5378 ms | 70776 KB | Output is correct |
63 | Correct | 5612 ms | 70776 KB | Output is correct |
64 | Correct | 2779 ms | 70776 KB | Output is correct |
65 | Correct | 3641 ms | 70776 KB | Output is correct |
66 | Correct | 3703 ms | 70776 KB | Output is correct |
67 | Correct | 5357 ms | 70776 KB | Output is correct |
68 | Correct | 5376 ms | 70776 KB | Output is correct |
69 | Correct | 5400 ms | 70776 KB | Output is correct |
70 | Correct | 5172 ms | 70776 KB | Output is correct |