# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
251035 | 2020-07-20T01:16:53 Z | gustjwkd1007 | Sushi (JOI16_sushi) | C++14 | 3850 ms | 262148 KB |
#include <bits/stdc++.h> #define buc 3 using namespace std; int n,q; int input[410000]; priority_queue <int> pq[410000/buc]; priority_queue <int,vector <int>,greater<int> > ms[410000/buc]; void showpq(int ind) { vector <int> now; while(!pq[ind].empty()) { printf("%d ",pq[ind].top()); now.push_back(pq[ind].top()); pq[ind].pop(); } for(int x : now) pq[ind].push(x); printf("\n"); } void show() { for(int i=0;i<n;i+=buc) { printf("%d : ",i); showpq(i/buc); } } void updatepq(int ind) { while(!pq[ind].empty()) pq[ind].pop(); for(int i=ind*buc;i<(ind+1)*buc;i++) pq[ind].push(input[i]); } void propa(int ind) { for(int i=ind*buc;i<(ind+1)*buc;i++) { ms[ind].push(input[i]); input[i]=ms[ind].top(); ms[ind].pop(); } while(!ms[ind].empty()) ms[ind].pop(); updatepq(ind); } int query(int st,int fin,int p) { if(st%buc) { propa(st/buc); for(;st%buc&&st<=fin;st++) { if(input[st]>p) swap(p,input[st]); } updatepq((st-1)/buc); } for(;st+buc-1<=fin;st+=buc) { ms[st/buc].push(p); pq[st/buc].push(p); p=pq[st/buc].top(); pq[st/buc].pop(); } if(st<=fin) { propa(st/buc); for(;st<=fin;st++) { if(input[st]>p) swap(p,input[st]); } updatepq(fin/buc); } return p; } int main() { scanf("%d %d",&n,&q); for(int i=0;i<n;i++) { scanf("%d",&input[i]); pq[i/buc].push(input[i]); } int s,t,p; for(int i=0;i<q;i++) { scanf("%d %d %d",&s,&t,&p); if(s<=t) printf("%d\n",query(s-1,t-1,p)); else printf("%d\n",query(0,t-1,query(s-1,n-1,p))); // for(int j=0;j<n;j++) // printf("%d ",input[j]); // printf("\n"); // show(); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 11000 KB | Output is correct |
2 | Correct | 63 ms | 11132 KB | Output is correct |
3 | Correct | 70 ms | 11128 KB | Output is correct |
4 | Correct | 62 ms | 11000 KB | Output is correct |
5 | Correct | 63 ms | 11000 KB | Output is correct |
6 | Correct | 66 ms | 11128 KB | Output is correct |
7 | Correct | 38 ms | 10876 KB | Output is correct |
8 | Correct | 36 ms | 11000 KB | Output is correct |
9 | Correct | 65 ms | 11128 KB | Output is correct |
10 | Correct | 64 ms | 11004 KB | Output is correct |
11 | Correct | 63 ms | 11124 KB | Output is correct |
12 | Correct | 62 ms | 11000 KB | Output is correct |
13 | Correct | 73 ms | 11132 KB | Output is correct |
14 | Correct | 120 ms | 14072 KB | Output is correct |
15 | Correct | 125 ms | 12920 KB | Output is correct |
16 | Correct | 8 ms | 8960 KB | Output is correct |
17 | Correct | 6 ms | 8960 KB | Output is correct |
18 | Correct | 5 ms | 8832 KB | Output is correct |
19 | Correct | 6 ms | 8832 KB | Output is correct |
20 | Correct | 6 ms | 8832 KB | Output is correct |
21 | Correct | 8 ms | 8832 KB | Output is correct |
22 | Correct | 6 ms | 8960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 3850 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 11000 KB | Output is correct |
2 | Correct | 63 ms | 11132 KB | Output is correct |
3 | Correct | 70 ms | 11128 KB | Output is correct |
4 | Correct | 62 ms | 11000 KB | Output is correct |
5 | Correct | 63 ms | 11000 KB | Output is correct |
6 | Correct | 66 ms | 11128 KB | Output is correct |
7 | Correct | 38 ms | 10876 KB | Output is correct |
8 | Correct | 36 ms | 11000 KB | Output is correct |
9 | Correct | 65 ms | 11128 KB | Output is correct |
10 | Correct | 64 ms | 11004 KB | Output is correct |
11 | Correct | 63 ms | 11124 KB | Output is correct |
12 | Correct | 62 ms | 11000 KB | Output is correct |
13 | Correct | 73 ms | 11132 KB | Output is correct |
14 | Correct | 120 ms | 14072 KB | Output is correct |
15 | Correct | 125 ms | 12920 KB | Output is correct |
16 | Correct | 8 ms | 8960 KB | Output is correct |
17 | Correct | 6 ms | 8960 KB | Output is correct |
18 | Correct | 5 ms | 8832 KB | Output is correct |
19 | Correct | 6 ms | 8832 KB | Output is correct |
20 | Correct | 6 ms | 8832 KB | Output is correct |
21 | Correct | 8 ms | 8832 KB | Output is correct |
22 | Correct | 6 ms | 8960 KB | Output is correct |
23 | Runtime error | 3850 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
24 | Halted | 0 ms | 0 KB | - |