# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
595755 | 2022-07-14T06:04:35 Z | Cross_Ratio | Sushi (JOI16_sushi) | C++14 | 4120 ms | 14712 KB |
#include <bits/stdc++.h> using namespace std; int A[400005]; int ans[400005]; int S[400005]; int T[400005]; int P[400005]; int SQ = 635; vector<int> idx; int id(int n) { return lower_bound(idx.begin(),idx.end(),n) - idx.begin(); } signed main() { cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; int i, j; for(i=0;i<N;i++) cin >> A[i]; int pt = 1; for(j=1;j<=Q;j++) { cin >> S[j] >> T[j] >> P[j]; S[j]--; T[j] %= N; if(j%SQ==0 || j == Q) { //cout << pt << " to " << j << '\n'; idx.clear(); for(i=pt;i<=j;i++) { idx.push_back(S[i]); idx.push_back(T[i]); } sort(idx.begin(),idx.end()); idx.erase(unique(idx.begin(),idx.end()),idx.end()); vector<priority_queue<int>> PQ; PQ.resize(idx.size()); for(i=0;i+1<idx.size();i++) { for(int m = idx[i]; m < idx[i+1]; m++) { PQ[i].push(A[m]); } } for(int m = idx[idx.size()-1];m<N;m++) { PQ[idx.size()-1].push(A[m]); } for(int m = 0; m < idx[0]; m++) { PQ[idx.size()-1].push(A[m]); } //cout <<"PQ init\n"; vector<priority_queue<int,vector<int>,greater<int>>> Push; Push.resize(idx.size()); for(i=pt;i<=j;i++) { int s = id(S[i]); int t = id(T[i]); int ans = P[i]; if(s<t) { for(int m = s; m < t; m++) { Push[m].push(ans); PQ[m].push(ans); ans = PQ[m].top(); PQ[m].pop(); } } else { for(int m = s; m < idx.size(); m++) { Push[m].push(ans); PQ[m].push(ans); ans = PQ[m].top(); PQ[m].pop(); } for(int m = 0; m < t; m++) { Push[m].push(ans); PQ[m].push(ans); ans = PQ[m].top(); PQ[m].pop(); } } cout << ans << '\n'; } for(i=0;i+1<idx.size();i++) { for(int m = idx[i]; m < idx[i+1]; m++) { Push[i].push(A[m]); A[m] = Push[i].top(); Push[i].pop(); } } for(int m = idx[idx.size()-1];m<N;m++) { Push[idx.size()-1].push(A[m]); A[m] = Push[idx.size()-1].top(); Push[idx.size()-1].pop(); } for(int m = 0; m <idx[0]; m++) { Push[idx.size()-1].push(A[m]); A[m] = Push[idx.size()-1].top(); Push[idx.size()-1].pop(); } pt = j + 1; } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 50 ms | 2532 KB | Output is correct |
2 | Correct | 45 ms | 2520 KB | Output is correct |
3 | Correct | 44 ms | 2596 KB | Output is correct |
4 | Correct | 37 ms | 2584 KB | Output is correct |
5 | Correct | 45 ms | 2648 KB | Output is correct |
6 | Correct | 39 ms | 2644 KB | Output is correct |
7 | Correct | 28 ms | 2520 KB | Output is correct |
8 | Correct | 28 ms | 2596 KB | Output is correct |
9 | Correct | 39 ms | 2600 KB | Output is correct |
10 | Correct | 38 ms | 2632 KB | Output is correct |
11 | Correct | 45 ms | 2644 KB | Output is correct |
12 | Correct | 45 ms | 2604 KB | Output is correct |
13 | Correct | 53 ms | 2772 KB | Output is correct |
14 | Correct | 43 ms | 2696 KB | Output is correct |
15 | Correct | 73 ms | 4768 KB | Output is correct |
16 | Correct | 4 ms | 524 KB | Output is correct |
17 | Correct | 0 ms | 328 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 340 KB | Output is correct |
20 | Correct | 0 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 328 KB | Output is correct |
22 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1135 ms | 8180 KB | Output is correct |
2 | Correct | 1091 ms | 9024 KB | Output is correct |
3 | Correct | 843 ms | 6996 KB | Output is correct |
4 | Correct | 1137 ms | 10520 KB | Output is correct |
5 | Correct | 1490 ms | 10456 KB | Output is correct |
6 | Correct | 1771 ms | 10588 KB | Output is correct |
7 | Correct | 1732 ms | 10480 KB | Output is correct |
8 | Correct | 1770 ms | 10460 KB | Output is correct |
9 | Correct | 547 ms | 6904 KB | Output is correct |
10 | Correct | 1515 ms | 9060 KB | Output is correct |
11 | Correct | 561 ms | 6928 KB | Output is correct |
12 | Correct | 1539 ms | 8984 KB | Output is correct |
13 | Correct | 1098 ms | 10348 KB | Output is correct |
14 | Correct | 1088 ms | 9020 KB | Output is correct |
15 | Correct | 825 ms | 6968 KB | Output is correct |
16 | Correct | 1057 ms | 10532 KB | Output is correct |
17 | Correct | 1520 ms | 10548 KB | Output is correct |
18 | Correct | 1737 ms | 10468 KB | Output is correct |
19 | Correct | 1742 ms | 10460 KB | Output is correct |
20 | Correct | 1751 ms | 10452 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 50 ms | 2532 KB | Output is correct |
2 | Correct | 45 ms | 2520 KB | Output is correct |
3 | Correct | 44 ms | 2596 KB | Output is correct |
4 | Correct | 37 ms | 2584 KB | Output is correct |
5 | Correct | 45 ms | 2648 KB | Output is correct |
6 | Correct | 39 ms | 2644 KB | Output is correct |
7 | Correct | 28 ms | 2520 KB | Output is correct |
8 | Correct | 28 ms | 2596 KB | Output is correct |
9 | Correct | 39 ms | 2600 KB | Output is correct |
10 | Correct | 38 ms | 2632 KB | Output is correct |
11 | Correct | 45 ms | 2644 KB | Output is correct |
12 | Correct | 45 ms | 2604 KB | Output is correct |
13 | Correct | 53 ms | 2772 KB | Output is correct |
14 | Correct | 43 ms | 2696 KB | Output is correct |
15 | Correct | 73 ms | 4768 KB | Output is correct |
16 | Correct | 4 ms | 524 KB | Output is correct |
17 | Correct | 0 ms | 328 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 340 KB | Output is correct |
20 | Correct | 0 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 328 KB | Output is correct |
22 | Correct | 1 ms | 340 KB | Output is correct |
23 | Correct | 1135 ms | 8180 KB | Output is correct |
24 | Correct | 1091 ms | 9024 KB | Output is correct |
25 | Correct | 843 ms | 6996 KB | Output is correct |
26 | Correct | 1137 ms | 10520 KB | Output is correct |
27 | Correct | 1490 ms | 10456 KB | Output is correct |
28 | Correct | 1771 ms | 10588 KB | Output is correct |
29 | Correct | 1732 ms | 10480 KB | Output is correct |
30 | Correct | 1770 ms | 10460 KB | Output is correct |
31 | Correct | 547 ms | 6904 KB | Output is correct |
32 | Correct | 1515 ms | 9060 KB | Output is correct |
33 | Correct | 561 ms | 6928 KB | Output is correct |
34 | Correct | 1539 ms | 8984 KB | Output is correct |
35 | Correct | 1098 ms | 10348 KB | Output is correct |
36 | Correct | 1088 ms | 9020 KB | Output is correct |
37 | Correct | 825 ms | 6968 KB | Output is correct |
38 | Correct | 1057 ms | 10532 KB | Output is correct |
39 | Correct | 1520 ms | 10548 KB | Output is correct |
40 | Correct | 1737 ms | 10468 KB | Output is correct |
41 | Correct | 1742 ms | 10460 KB | Output is correct |
42 | Correct | 1751 ms | 10452 KB | Output is correct |
43 | Correct | 2517 ms | 12012 KB | Output is correct |
44 | Correct | 2372 ms | 11956 KB | Output is correct |
45 | Correct | 1653 ms | 8628 KB | Output is correct |
46 | Correct | 2471 ms | 12072 KB | Output is correct |
47 | Correct | 2469 ms | 12172 KB | Output is correct |
48 | Correct | 2613 ms | 12248 KB | Output is correct |
49 | Correct | 2740 ms | 12152 KB | Output is correct |
50 | Correct | 2614 ms | 12036 KB | Output is correct |
51 | Correct | 2685 ms | 12204 KB | Output is correct |
52 | Correct | 2414 ms | 11812 KB | Output is correct |
53 | Correct | 3468 ms | 14668 KB | Output is correct |
54 | Correct | 3646 ms | 14648 KB | Output is correct |
55 | Correct | 3838 ms | 14704 KB | Output is correct |
56 | Correct | 3886 ms | 14664 KB | Output is correct |
57 | Correct | 4120 ms | 14712 KB | Output is correct |
58 | Correct | 1934 ms | 10468 KB | Output is correct |
59 | Correct | 2028 ms | 10584 KB | Output is correct |
60 | Correct | 1795 ms | 10984 KB | Output is correct |
61 | Correct | 1941 ms | 10932 KB | Output is correct |
62 | Correct | 1916 ms | 10884 KB | Output is correct |
63 | Correct | 1898 ms | 10816 KB | Output is correct |
64 | Correct | 1385 ms | 8464 KB | Output is correct |
65 | Correct | 1751 ms | 9440 KB | Output is correct |
66 | Correct | 1611 ms | 9644 KB | Output is correct |
67 | Correct | 2178 ms | 13824 KB | Output is correct |
68 | Correct | 2553 ms | 13920 KB | Output is correct |
69 | Correct | 2495 ms | 13864 KB | Output is correct |
70 | Correct | 2603 ms | 13840 KB | Output is correct |