oj.uz

Submission #734776

# Submission time Handle Problem Language Result Execution time Memory
734776 2023-05-03T05:08:34 Z abcvuitunggio Sushi (JOI16_sushi) C++17
100 / 100
 3909 ms 78700 KB 
#include <bits/stdc++.h>
#define pq priority_queue
using namespace std;
const int sz=632;
pq <int> q[633];
pq <int, vector <int>, greater <int>> p[633];
int n,m,x[400000],s,t,cur;
void reset(int i){
    for (int j=i*sz;j<min(i*sz+sz,n);j++){
        p[i].push(x[j]);
        x[j]=p[i].top();
        p[i].pop();
    }
    p[i]=pq <int, vector <int>, greater <int>>();
    q[i]=pq <int>();
}
void f(int l, int r){
    int b=l/sz,e=r/sz;
    reset(b);
    for (int i=l;i<min(b*sz+sz,r+1);i++)
        if (x[i]>cur)
            swap(x[i],cur);
    for (int i=b*sz;i<min(b*sz+sz,n);i++)
        q[b].push(x[i]);
    if (b==e)
        return;
    for (int i=b+1;i<e;i++){
        p[i].push(cur);
        q[i].push(cur);
        cur=q[i].top();
        q[i].pop();
    }
    reset(e);
    for (int i=e*sz;i<=r;i++)
        if (x[i]>cur)
            swap(x[i],cur);
    for (int i=e*sz;i<min(e*sz+sz,n);i++)
        q[e].push(x[i]);
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m;
    for (int i=0;i<n;i++){
        cin >> x[i];
        q[i/sz].push(x[i]);
    }
    while (m--){
        cin >> s >> t >> cur;
        s--;
        t--;
        if (s<=t)
            f(s,t);
        else{
            f(s,n-1);
            f(0,t);
        }
        cout << cur << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 340 KB Output is correct
2 Correct 63 ms 404 KB Output is correct
3 Correct 63 ms 408 KB Output is correct
4 Correct 67 ms 404 KB Output is correct
5 Correct 65 ms 428 KB Output is correct
6 Correct 66 ms 384 KB Output is correct
7 Correct 58 ms 400 KB Output is correct
8 Correct 56 ms 396 KB Output is correct
9 Correct 64 ms 416 KB Output is correct
10 Correct 64 ms 340 KB Output is correct
11 Correct 73 ms 400 KB Output is correct
12 Correct 85 ms 392 KB Output is correct
13 Correct 85 ms 400 KB Output is correct
14 Correct 84 ms 396 KB Output is correct
15 Correct 89 ms 392 KB Output is correct
16 Correct 28 ms 404 KB Output is correct
17 Correct 0 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 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2795 ms 77340 KB Output is correct
2 Correct 2818 ms 77436 KB Output is correct
3 Correct 1509 ms 77228 KB Output is correct
4 Correct 2828 ms 78572 KB Output is correct
5 Correct 2583 ms 78552 KB Output is correct
6 Correct 2986 ms 78464 KB Output is correct
7 Correct 3028 ms 78596 KB Output is correct
8 Correct 2929 ms 77952 KB Output is correct
9 Correct 1390 ms 78196 KB Output is correct
10 Correct 2390 ms 78428 KB Output is correct
11 Correct 1356 ms 78236 KB Output is correct
12 Correct 2497 ms 77428 KB Output is correct
13 Correct 2828 ms 78552 KB Output is correct
14 Correct 2830 ms 78600 KB Output is correct
15 Correct 1645 ms 78200 KB Output is correct
16 Correct 2775 ms 78520 KB Output is correct
17 Correct 2388 ms 78400 KB Output is correct
18 Correct 2846 ms 78600 KB Output is correct
19 Correct 2846 ms 78520 KB Output is correct
20 Correct 2873 ms 78700 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 340 KB Output is correct
2 Correct 63 ms 404 KB Output is correct
3 Correct 63 ms 408 KB Output is correct
4 Correct 67 ms 404 KB Output is correct
5 Correct 65 ms 428 KB Output is correct
6 Correct 66 ms 384 KB Output is correct
7 Correct 58 ms 400 KB Output is correct
8 Correct 56 ms 396 KB Output is correct
9 Correct 64 ms 416 KB Output is correct
10 Correct 64 ms 340 KB Output is correct
11 Correct 73 ms 400 KB Output is correct
12 Correct 85 ms 392 KB Output is correct
13 Correct 85 ms 400 KB Output is correct
14 Correct 84 ms 396 KB Output is correct
15 Correct 89 ms 392 KB Output is correct
16 Correct 28 ms 404 KB Output is correct
17 Correct 0 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 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2795 ms 77340 KB Output is correct
24 Correct 2818 ms 77436 KB Output is correct
25 Correct 1509 ms 77228 KB Output is correct
26 Correct 2828 ms 78572 KB Output is correct
27 Correct 2583 ms 78552 KB Output is correct
28 Correct 2986 ms 78464 KB Output is correct
29 Correct 3028 ms 78596 KB Output is correct
30 Correct 2929 ms 77952 KB Output is correct
31 Correct 1390 ms 78196 KB Output is correct
32 Correct 2390 ms 78428 KB Output is correct
33 Correct 1356 ms 78236 KB Output is correct
34 Correct 2497 ms 77428 KB Output is correct
35 Correct 2828 ms 78552 KB Output is correct
36 Correct 2830 ms 78600 KB Output is correct
37 Correct 1645 ms 78200 KB Output is correct
38 Correct 2775 ms 78520 KB Output is correct
39 Correct 2388 ms 78400 KB Output is correct
40 Correct 2846 ms 78600 KB Output is correct
41 Correct 2846 ms 78520 KB Output is correct
42 Correct 2873 ms 78700 KB Output is correct
43 Correct 2296 ms 5848 KB Output is correct
44 Correct 2265 ms 6912 KB Output is correct
45 Correct 1835 ms 6360 KB Output is correct
46 Correct 2308 ms 6664 KB Output is correct
47 Correct 2309 ms 6664 KB Output is correct
48 Correct 2943 ms 6568 KB Output is correct
49 Correct 3241 ms 6588 KB Output is correct
50 Correct 3192 ms 6592 KB Output is correct
51 Correct 3180 ms 6620 KB Output is correct
52 Correct 3191 ms 8540 KB Output is correct
53 Correct 3000 ms 8472 KB Output is correct
54 Correct 3648 ms 8428 KB Output is correct
55 Correct 3909 ms 8408 KB Output is correct
56 Correct 3824 ms 8380 KB Output is correct
57 Correct 3867 ms 8572 KB Output is correct
58 Correct 2233 ms 7412 KB Output is correct
59 Correct 2206 ms 7280 KB Output is correct
60 Correct 2420 ms 78412 KB Output is correct
61 Correct 2791 ms 78220 KB Output is correct
62 Correct 2837 ms 78172 KB Output is correct
63 Correct 2711 ms 78156 KB Output is correct
64 Correct 1324 ms 6092 KB Output is correct
65 Correct 1436 ms 42552 KB Output is correct
66 Correct 1438 ms 42832 KB Output is correct
67 Correct 3277 ms 47168 KB Output is correct
68 Correct 3709 ms 47008 KB Output is correct
69 Correct 3725 ms 46928 KB Output is correct
70 Correct 3542 ms 46848 KB Output is correct