| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55912 |
2018-07-09T07:21:54 Z |
윤교준(#1564) |
Sushi (JOI16_sushi) |
C++11 |
|
5930 ms |
122396 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_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 INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
const bool debug = 0;
const int MAXN = 400005;
const int MAXQ = 25005;
const int SQRN = 655;
struct BUK {
priority_queue<int, vector<int>, greater<int>> QV;
priority_queue<int> PQ;
int A[SQRN];
int S, E, N;
int cal(int s, int e, int x) {
for(int i = s; i <= e; i++)
if(x < A[i]) swap(A[i], x);
return x;
}
int f(int p, int q, int x) {
p = max(S, p); q = min(E, q);
if(p > q) return x;
if(PQ.top() <= x) return x;
if(p <= S && E <= q) {
QV.push(x);
int ret = PQ.top(); PQ.pop();
PQ.push(x);
return ret;
}
if(!QV.empty()) {
for(int i = 0; i < N; i++) {
if(A[i] <= QV.top()) continue;
int t = QV.top(); QV.pop();
QV.push(A[i]);
A[i] = t;
}
for(; !QV.empty(); QV.pop());
}
int ret = cal(p-S, q-S, x);
for(; !PQ.empty(); PQ.pop());
for(int i = 0; i < N; i++)
PQ.push(A[i]);
return ret;
}
} buk[SQRN]; int bukn;
int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];
int N, Q;
int main() {
ios::sync_with_stdio(false);
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> A[i];
for(int i = 1; i <= Q; i++) cin >> B[i] >> C[i] >> D[i];
for(int i = 1, s, e;; i++) {
s = (i-1)*SQRN + 1;
e = min(N, i*SQRN);
if(s > e) break;
buk[i].S = s; buk[i].E = e;
buk[i].N = e-s+1;
for(int j = s; j <= e; j++) {
buk[i].A[j-s] = A[j];
buk[i].PQ.push(A[j]);
}
bukn = i;
}
if(debug) {
printf("bukn=%d\n", bukn);
for(int i = 1; i <= bukn; i++) {
printf("%d buk : %d %d %d\n", i, buk[i].S, buk[i].E, buk[i].N);
for(int j = 0; j < buk[i].N; j++) printf("%d ", buk[i].A[j]);
puts("");
}
}
for(int qi = 1, s, e, x; qi <= Q; qi++) {
s = B[qi]; e = C[qi]; x = D[qi];
if(s <= e) {
for(int i = 1; i <= bukn; i++)
x = buk[i].f(s, e, x);
} else {
for(int i = 1; i <= bukn; i++) {
x = buk[i].f(s, N, x);
}
for(int i = 1; i <= bukn; i++)
x = buk[i].f(1, e, x);
}
printf("%d\n", x);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
2168 KB |
Output is correct |
| 2 |
Correct |
122 ms |
2348 KB |
Output is correct |
| 3 |
Correct |
116 ms |
2380 KB |
Output is correct |
| 4 |
Correct |
133 ms |
2380 KB |
Output is correct |
| 5 |
Correct |
122 ms |
2380 KB |
Output is correct |
| 6 |
Correct |
131 ms |
2380 KB |
Output is correct |
| 7 |
Correct |
30 ms |
2464 KB |
Output is correct |
| 8 |
Correct |
29 ms |
2464 KB |
Output is correct |
| 9 |
Correct |
130 ms |
2492 KB |
Output is correct |
| 10 |
Correct |
119 ms |
2512 KB |
Output is correct |
| 11 |
Correct |
164 ms |
2536 KB |
Output is correct |
| 12 |
Correct |
162 ms |
2536 KB |
Output is correct |
| 13 |
Correct |
173 ms |
2676 KB |
Output is correct |
| 14 |
Correct |
102 ms |
2676 KB |
Output is correct |
| 15 |
Correct |
96 ms |
2676 KB |
Output is correct |
| 16 |
Correct |
131 ms |
2676 KB |
Output is correct |
| 17 |
Correct |
5 ms |
2676 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2676 KB |
Output is correct |
| 19 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2676 KB |
Output is correct |
| 21 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 22 |
Correct |
4 ms |
2676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3162 ms |
78064 KB |
Output is correct |
| 2 |
Correct |
3024 ms |
78064 KB |
Output is correct |
| 3 |
Correct |
125 ms |
78064 KB |
Output is correct |
| 4 |
Correct |
3183 ms |
78132 KB |
Output is correct |
| 5 |
Correct |
2904 ms |
78132 KB |
Output is correct |
| 6 |
Correct |
3404 ms |
78132 KB |
Output is correct |
| 7 |
Correct |
3354 ms |
78132 KB |
Output is correct |
| 8 |
Correct |
3543 ms |
78132 KB |
Output is correct |
| 9 |
Correct |
120 ms |
78132 KB |
Output is correct |
| 10 |
Correct |
2871 ms |
78132 KB |
Output is correct |
| 11 |
Correct |
122 ms |
78132 KB |
Output is correct |
| 12 |
Correct |
2588 ms |
78132 KB |
Output is correct |
| 13 |
Correct |
2879 ms |
78132 KB |
Output is correct |
| 14 |
Correct |
3447 ms |
78528 KB |
Output is correct |
| 15 |
Correct |
124 ms |
78528 KB |
Output is correct |
| 16 |
Correct |
3020 ms |
78584 KB |
Output is correct |
| 17 |
Correct |
2824 ms |
78584 KB |
Output is correct |
| 18 |
Correct |
3608 ms |
78584 KB |
Output is correct |
| 19 |
Correct |
3408 ms |
78584 KB |
Output is correct |
| 20 |
Correct |
3385 ms |
78584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
2168 KB |
Output is correct |
| 2 |
Correct |
122 ms |
2348 KB |
Output is correct |
| 3 |
Correct |
116 ms |
2380 KB |
Output is correct |
| 4 |
Correct |
133 ms |
2380 KB |
Output is correct |
| 5 |
Correct |
122 ms |
2380 KB |
Output is correct |
| 6 |
Correct |
131 ms |
2380 KB |
Output is correct |
| 7 |
Correct |
30 ms |
2464 KB |
Output is correct |
| 8 |
Correct |
29 ms |
2464 KB |
Output is correct |
| 9 |
Correct |
130 ms |
2492 KB |
Output is correct |
| 10 |
Correct |
119 ms |
2512 KB |
Output is correct |
| 11 |
Correct |
164 ms |
2536 KB |
Output is correct |
| 12 |
Correct |
162 ms |
2536 KB |
Output is correct |
| 13 |
Correct |
173 ms |
2676 KB |
Output is correct |
| 14 |
Correct |
102 ms |
2676 KB |
Output is correct |
| 15 |
Correct |
96 ms |
2676 KB |
Output is correct |
| 16 |
Correct |
131 ms |
2676 KB |
Output is correct |
| 17 |
Correct |
5 ms |
2676 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2676 KB |
Output is correct |
| 19 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2676 KB |
Output is correct |
| 21 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 22 |
Correct |
4 ms |
2676 KB |
Output is correct |
| 23 |
Correct |
3162 ms |
78064 KB |
Output is correct |
| 24 |
Correct |
3024 ms |
78064 KB |
Output is correct |
| 25 |
Correct |
125 ms |
78064 KB |
Output is correct |
| 26 |
Correct |
3183 ms |
78132 KB |
Output is correct |
| 27 |
Correct |
2904 ms |
78132 KB |
Output is correct |
| 28 |
Correct |
3404 ms |
78132 KB |
Output is correct |
| 29 |
Correct |
3354 ms |
78132 KB |
Output is correct |
| 30 |
Correct |
3543 ms |
78132 KB |
Output is correct |
| 31 |
Correct |
120 ms |
78132 KB |
Output is correct |
| 32 |
Correct |
2871 ms |
78132 KB |
Output is correct |
| 33 |
Correct |
122 ms |
78132 KB |
Output is correct |
| 34 |
Correct |
2588 ms |
78132 KB |
Output is correct |
| 35 |
Correct |
2879 ms |
78132 KB |
Output is correct |
| 36 |
Correct |
3447 ms |
78528 KB |
Output is correct |
| 37 |
Correct |
124 ms |
78528 KB |
Output is correct |
| 38 |
Correct |
3020 ms |
78584 KB |
Output is correct |
| 39 |
Correct |
2824 ms |
78584 KB |
Output is correct |
| 40 |
Correct |
3608 ms |
78584 KB |
Output is correct |
| 41 |
Correct |
3408 ms |
78584 KB |
Output is correct |
| 42 |
Correct |
3385 ms |
78584 KB |
Output is correct |
| 43 |
Correct |
1989 ms |
78584 KB |
Output is correct |
| 44 |
Correct |
1936 ms |
78584 KB |
Output is correct |
| 45 |
Correct |
527 ms |
78584 KB |
Output is correct |
| 46 |
Correct |
1941 ms |
78584 KB |
Output is correct |
| 47 |
Correct |
1937 ms |
78584 KB |
Output is correct |
| 48 |
Correct |
4755 ms |
78584 KB |
Output is correct |
| 49 |
Correct |
4546 ms |
78584 KB |
Output is correct |
| 50 |
Correct |
4925 ms |
78584 KB |
Output is correct |
| 51 |
Correct |
4934 ms |
78584 KB |
Output is correct |
| 52 |
Correct |
1972 ms |
78584 KB |
Output is correct |
| 53 |
Correct |
2041 ms |
78584 KB |
Output is correct |
| 54 |
Correct |
3985 ms |
78584 KB |
Output is correct |
| 55 |
Correct |
4430 ms |
78584 KB |
Output is correct |
| 56 |
Correct |
4066 ms |
78584 KB |
Output is correct |
| 57 |
Correct |
4206 ms |
78584 KB |
Output is correct |
| 58 |
Correct |
4304 ms |
78584 KB |
Output is correct |
| 59 |
Correct |
4142 ms |
78584 KB |
Output is correct |
| 60 |
Correct |
5531 ms |
122396 KB |
Output is correct |
| 61 |
Correct |
5784 ms |
122396 KB |
Output is correct |
| 62 |
Correct |
5917 ms |
122396 KB |
Output is correct |
| 63 |
Correct |
5930 ms |
122396 KB |
Output is correct |
| 64 |
Correct |
728 ms |
122396 KB |
Output is correct |
| 65 |
Correct |
1612 ms |
122396 KB |
Output is correct |
| 66 |
Correct |
1715 ms |
122396 KB |
Output is correct |
| 67 |
Correct |
3624 ms |
122396 KB |
Output is correct |
| 68 |
Correct |
3451 ms |
122396 KB |
Output is correct |
| 69 |
Correct |
3688 ms |
122396 KB |
Output is correct |
| 70 |
Correct |
3405 ms |
122396 KB |
Output is correct |
