oj.uz

Submission #152437

# Submission time Handle Problem Language Result Execution time Memory
152437 2019-09-08T02:27:12 Z arnold518 Sushi (JOI16_sushi) C++14
100 / 100
 11431 ms 144352 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 400000;
const int MAXQ = 25000;

int N, Q, A[MAXN+10], SQ;
priority_queue<int> PQ1[MAXN+10];
priority_queue<int, vector<int>, greater<int>> PQ2[MAXN+10];

void solve(int S, int T, int &P)
{
    int i, j;
    if(S/SQ==T/SQ)
    {
        int l=max(1, S/SQ*SQ), r=min(N, S/SQ*SQ+SQ-1);
        for(i=l; i<=r; i++)
        {
            PQ2[S/SQ].push(A[i]);
            A[i]=PQ2[S/SQ].top(); PQ2[S/SQ].pop();
        }
        while(!PQ2[S/SQ].empty()) PQ2[S/SQ].pop();
        while(!PQ1[S/SQ].empty()) PQ1[S/SQ].pop();
        for(i=S; i<=T; i++) if(P<A[i]) swap(A[i], P);
        for(i=l; i<=r; i++) PQ1[S/SQ].push(A[i]);
    }
    else
    {
        int l, r;
        l=max(1, S/SQ*SQ), r=min(N, S/SQ*SQ+SQ-1);
        for(i=l; i<=r; i++)
        {
            PQ2[S/SQ].push(A[i]);
            A[i]=PQ2[S/SQ].top(); PQ2[S/SQ].pop();
        }
        while(!PQ2[S/SQ].empty()) PQ2[S/SQ].pop();
        while(!PQ1[S/SQ].empty()) PQ1[S/SQ].pop();
        for(i=S; i<=r; i++) if(P<A[i]) swap(A[i], P);
        for(i=l; i<=r; i++) PQ1[S/SQ].push(A[i]);

        for(i=S/SQ+1; i<T/SQ; i++)
        {
            PQ1[i].push(P);
            PQ2[i].push(P);
            P=PQ1[i].top();
            PQ1[i].pop();
        }

        l=max(1, T/SQ*SQ), r=min(N, T/SQ*SQ+SQ-1);
        for(i=l; i<=r; i++)
        {
            PQ2[T/SQ].push(A[i]);
            A[i]=PQ2[T/SQ].top(); PQ2[T/SQ].pop();
        }
        while(!PQ2[T/SQ].empty()) PQ2[T/SQ].pop();
        while(!PQ1[T/SQ].empty()) PQ1[T/SQ].pop();
        for(i=l; i<=T; i++) if(P<A[i]) swap(A[i], P);
        for(i=l; i<=r; i++) PQ1[T/SQ].push(A[i]);
    }
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    SQ=400;

    priority_queue<int> PQ;
    for(i=1; i<=N; i++)
    {
        scanf("%d", &A[i]);
        PQ1[i/SQ].push(A[i]);
    }

    while(Q--)
    {
        int S, T, P;
        scanf("%d%d%d", &S, &T, &P);
        if(S<=T) solve(S, T, P);
        else
        {
            solve(S, N, P);
            solve(1, T, P);
        }
        printf("%d\n", P);
    }
}

Compilation message

sushi.cpp: In function 'void solve(int, int, int&)':
sushi.cpp:17:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sushi.cpp: In function 'int main()':
sushi.cpp:68:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sushi.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
sushi.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &S, &T, &P);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 25452 KB Output is correct
2 Correct 302 ms 25456 KB Output is correct
3 Correct 301 ms 25572 KB Output is correct
4 Correct 269 ms 25472 KB Output is correct
5 Correct 299 ms 25464 KB Output is correct
6 Correct 303 ms 25464 KB Output is correct
7 Correct 199 ms 25436 KB Output is correct
8 Correct 181 ms 25428 KB Output is correct
9 Correct 301 ms 25564 KB Output is correct
10 Correct 302 ms 25464 KB Output is correct
11 Correct 298 ms 25464 KB Output is correct
12 Correct 275 ms 25468 KB Output is correct
13 Correct 308 ms 25464 KB Output is correct
14 Correct 399 ms 25464 KB Output is correct
15 Correct 409 ms 25464 KB Output is correct
16 Correct 134 ms 25476 KB Output is correct
17 Correct 29 ms 25364 KB Output is correct
18 Correct 29 ms 25340 KB Output is correct
19 Correct 25 ms 25336 KB Output is correct
20 Correct 25 ms 25336 KB Output is correct
21 Correct 29 ms 25312 KB Output is correct
22 Correct 27 ms 25324 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7334 ms 144256 KB Output is correct
2 Correct 7299 ms 143920 KB Output is correct
3 Correct 3885 ms 143968 KB Output is correct
4 Correct 7200 ms 144184 KB Output is correct
5 Correct 5058 ms 144252 KB Output is correct
6 Correct 7504 ms 144212 KB Output is correct
7 Correct 7372 ms 144196 KB Output is correct
8 Correct 7397 ms 144144 KB Output is correct
9 Correct 3598 ms 143924 KB Output is correct
10 Correct 5002 ms 144280 KB Output is correct
11 Correct 3667 ms 143852 KB Output is correct
12 Correct 6394 ms 144096 KB Output is correct
13 Correct 7131 ms 144112 KB Output is correct
14 Correct 7425 ms 144060 KB Output is correct
15 Correct 3046 ms 144068 KB Output is correct
16 Correct 7266 ms 144020 KB Output is correct
17 Correct 6514 ms 144044 KB Output is correct
18 Correct 7480 ms 144044 KB Output is correct
19 Correct 7474 ms 143984 KB Output is correct
20 Correct 6148 ms 144352 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 25452 KB Output is correct
2 Correct 302 ms 25456 KB Output is correct
3 Correct 301 ms 25572 KB Output is correct
4 Correct 269 ms 25472 KB Output is correct
5 Correct 299 ms 25464 KB Output is correct
6 Correct 303 ms 25464 KB Output is correct
7 Correct 199 ms 25436 KB Output is correct
8 Correct 181 ms 25428 KB Output is correct
9 Correct 301 ms 25564 KB Output is correct
10 Correct 302 ms 25464 KB Output is correct
11 Correct 298 ms 25464 KB Output is correct
12 Correct 275 ms 25468 KB Output is correct
13 Correct 308 ms 25464 KB Output is correct
14 Correct 399 ms 25464 KB Output is correct
15 Correct 409 ms 25464 KB Output is correct
16 Correct 134 ms 25476 KB Output is correct
17 Correct 29 ms 25364 KB Output is correct
18 Correct 29 ms 25340 KB Output is correct
19 Correct 25 ms 25336 KB Output is correct
20 Correct 25 ms 25336 KB Output is correct
21 Correct 29 ms 25312 KB Output is correct
22 Correct 27 ms 25324 KB Output is correct
23 Correct 7334 ms 144256 KB Output is correct
24 Correct 7299 ms 143920 KB Output is correct
25 Correct 3885 ms 143968 KB Output is correct
26 Correct 7200 ms 144184 KB Output is correct
27 Correct 5058 ms 144252 KB Output is correct
28 Correct 7504 ms 144212 KB Output is correct
29 Correct 7372 ms 144196 KB Output is correct
30 Correct 7397 ms 144144 KB Output is correct
31 Correct 3598 ms 143924 KB Output is correct
32 Correct 5002 ms 144280 KB Output is correct
33 Correct 3667 ms 143852 KB Output is correct
34 Correct 6394 ms 144096 KB Output is correct
35 Correct 7131 ms 144112 KB Output is correct
36 Correct 7425 ms 144060 KB Output is correct
37 Correct 3046 ms 144068 KB Output is correct
38 Correct 7266 ms 144020 KB Output is correct
39 Correct 6514 ms 144044 KB Output is correct
40 Correct 7480 ms 144044 KB Output is correct
41 Correct 7474 ms 143984 KB Output is correct
42 Correct 6148 ms 144352 KB Output is correct
43 Correct 7275 ms 37276 KB Output is correct
44 Correct 7312 ms 36456 KB Output is correct
45 Correct 4935 ms 36356 KB Output is correct
46 Correct 6604 ms 36516 KB Output is correct
47 Correct 7290 ms 36416 KB Output is correct
48 Correct 7649 ms 36748 KB Output is correct
49 Correct 7878 ms 36436 KB Output is correct
50 Correct 7127 ms 36908 KB Output is correct
51 Correct 7824 ms 36868 KB Output is correct
52 Correct 11153 ms 50424 KB Output is correct
53 Correct 10811 ms 48468 KB Output is correct
54 Correct 9779 ms 48324 KB Output is correct
55 Correct 11317 ms 48952 KB Output is correct
56 Correct 11346 ms 48672 KB Output is correct
57 Correct 11431 ms 48828 KB Output is correct
58 Correct 5905 ms 40364 KB Output is correct
59 Correct 5965 ms 40184 KB Output is correct
60 Correct 6519 ms 144276 KB Output is correct
61 Correct 7487 ms 144068 KB Output is correct
62 Correct 7465 ms 144256 KB Output is correct
63 Correct 7425 ms 143940 KB Output is correct
64 Correct 4112 ms 36364 KB Output is correct
65 Correct 4713 ms 87820 KB Output is correct
66 Correct 4525 ms 87628 KB Output is correct
67 Correct 10130 ms 121724 KB Output is correct
68 Correct 10773 ms 121832 KB Output is correct
69 Correct 10668 ms 121884 KB Output is correct
70 Correct 9382 ms 121892 KB Output is correct