oj.uz

Submission #152430

# Submission time Handle Problem Language Result Execution time Memory
152430 2019-09-08T02:15:44 Z arnold518 Sushi (JOI16_sushi) C++14
100 / 100
 11266 ms 145480 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];

int 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]);
    }
    return P;
}

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) printf("%d\n", solve(S, T, P));
        else
        {
            P=solve(S, N, P);
            printf("%d\n", solve(1, T, P));
        }
/*
        for(i=0; i<=N/SQ; i++)
        {
            printf("bucket : %d\n", i);
            vector<int> V;
            printf("PQ1 : ");
            while(!PQ1[i].empty()) printf("%d ", PQ1[i].top()), V.push_back(PQ1[i].top()), PQ1[i].pop(); printf("\n");
            while(!V.empty()) PQ1[i].push(V.back()), V.pop_back();
            printf("PQ2 : ");
            while(!PQ2[i].empty()) printf("%d ", PQ2[i].top()), V.push_back(PQ2[i].top()), PQ2[i].pop(); printf("\n");
            while(!V.empty()) PQ2[i].push(V.back()), V.pop_back();
        }
        for(i=1; i<=N; i++) printf("%d ", A[i]); printf("\n");
        printf("============\n");
*/
    }
}

Compilation message

sushi.cpp: In function 'int 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:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
sushi.cpp:71: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:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
sushi.cpp:84: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 303 ms 25544 KB Output is correct
2 Correct 311 ms 25592 KB Output is correct
3 Correct 306 ms 25600 KB Output is correct
4 Correct 266 ms 25464 KB Output is correct
5 Correct 302 ms 25464 KB Output is correct
6 Correct 306 ms 25464 KB Output is correct
7 Correct 203 ms 25464 KB Output is correct
8 Correct 184 ms 25464 KB Output is correct
9 Correct 302 ms 25600 KB Output is correct
10 Correct 299 ms 25464 KB Output is correct
11 Correct 301 ms 25720 KB Output is correct
12 Correct 269 ms 25592 KB Output is correct
13 Correct 310 ms 25464 KB Output is correct
14 Correct 405 ms 25572 KB Output is correct
15 Correct 402 ms 25732 KB Output is correct
16 Correct 133 ms 25592 KB Output is correct
17 Correct 25 ms 25464 KB Output is correct
18 Correct 25 ms 25372 KB Output is correct
19 Correct 25 ms 25464 KB Output is correct
20 Correct 25 ms 25336 KB Output is correct
21 Correct 25 ms 25336 KB Output is correct
22 Correct 25 ms 25372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7353 ms 145356 KB Output is correct
2 Correct 7350 ms 145208 KB Output is correct
3 Correct 4018 ms 145028 KB Output is correct
4 Correct 7383 ms 145348 KB Output is correct
5 Correct 5248 ms 145480 KB Output is correct
6 Correct 7626 ms 145304 KB Output is correct
7 Correct 7578 ms 145256 KB Output is correct
8 Correct 7577 ms 145036 KB Output is correct
9 Correct 3704 ms 144912 KB Output is correct
10 Correct 5124 ms 145144 KB Output is correct
11 Correct 3682 ms 145008 KB Output is correct
12 Correct 6544 ms 144936 KB Output is correct
13 Correct 7336 ms 145128 KB Output is correct
14 Correct 7348 ms 144908 KB Output is correct
15 Correct 3092 ms 144880 KB Output is correct
16 Correct 7347 ms 144820 KB Output is correct
17 Correct 6518 ms 144736 KB Output is correct
18 Correct 7535 ms 144644 KB Output is correct
19 Correct 7504 ms 144644 KB Output is correct
20 Correct 6229 ms 144936 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 25544 KB Output is correct
2 Correct 311 ms 25592 KB Output is correct
3 Correct 306 ms 25600 KB Output is correct
4 Correct 266 ms 25464 KB Output is correct
5 Correct 302 ms 25464 KB Output is correct
6 Correct 306 ms 25464 KB Output is correct
7 Correct 203 ms 25464 KB Output is correct
8 Correct 184 ms 25464 KB Output is correct
9 Correct 302 ms 25600 KB Output is correct
10 Correct 299 ms 25464 KB Output is correct
11 Correct 301 ms 25720 KB Output is correct
12 Correct 269 ms 25592 KB Output is correct
13 Correct 310 ms 25464 KB Output is correct
14 Correct 405 ms 25572 KB Output is correct
15 Correct 402 ms 25732 KB Output is correct
16 Correct 133 ms 25592 KB Output is correct
17 Correct 25 ms 25464 KB Output is correct
18 Correct 25 ms 25372 KB Output is correct
19 Correct 25 ms 25464 KB Output is correct
20 Correct 25 ms 25336 KB Output is correct
21 Correct 25 ms 25336 KB Output is correct
22 Correct 25 ms 25372 KB Output is correct
23 Correct 7353 ms 145356 KB Output is correct
24 Correct 7350 ms 145208 KB Output is correct
25 Correct 4018 ms 145028 KB Output is correct
26 Correct 7383 ms 145348 KB Output is correct
27 Correct 5248 ms 145480 KB Output is correct
28 Correct 7626 ms 145304 KB Output is correct
29 Correct 7578 ms 145256 KB Output is correct
30 Correct 7577 ms 145036 KB Output is correct
31 Correct 3704 ms 144912 KB Output is correct
32 Correct 5124 ms 145144 KB Output is correct
33 Correct 3682 ms 145008 KB Output is correct
34 Correct 6544 ms 144936 KB Output is correct
35 Correct 7336 ms 145128 KB Output is correct
36 Correct 7348 ms 144908 KB Output is correct
37 Correct 3092 ms 144880 KB Output is correct
38 Correct 7347 ms 144820 KB Output is correct
39 Correct 6518 ms 144736 KB Output is correct
40 Correct 7535 ms 144644 KB Output is correct
41 Correct 7504 ms 144644 KB Output is correct
42 Correct 6229 ms 144936 KB Output is correct
43 Correct 7236 ms 37204 KB Output is correct
44 Correct 7130 ms 37020 KB Output is correct
45 Correct 4842 ms 36940 KB Output is correct
46 Correct 6540 ms 36648 KB Output is correct
47 Correct 7127 ms 36724 KB Output is correct
48 Correct 7576 ms 37064 KB Output is correct
49 Correct 7802 ms 36772 KB Output is correct
50 Correct 7124 ms 37408 KB Output is correct
51 Correct 7813 ms 37308 KB Output is correct
52 Correct 11078 ms 51152 KB Output is correct
53 Correct 10659 ms 48776 KB Output is correct
54 Correct 9703 ms 48640 KB Output is correct
55 Correct 11203 ms 49332 KB Output is correct
56 Correct 11180 ms 48980 KB Output is correct
57 Correct 11266 ms 49032 KB Output is correct
58 Correct 5876 ms 40500 KB Output is correct
59 Correct 5962 ms 40216 KB Output is correct
60 Correct 6564 ms 144216 KB Output is correct
61 Correct 7426 ms 144000 KB Output is correct
62 Correct 7547 ms 143968 KB Output is correct
63 Correct 7400 ms 144072 KB Output is correct
64 Correct 4070 ms 36436 KB Output is correct
65 Correct 4740 ms 87768 KB Output is correct
66 Correct 4487 ms 87648 KB Output is correct
67 Correct 10036 ms 121844 KB Output is correct
68 Correct 10665 ms 121900 KB Output is correct
69 Correct 10722 ms 121804 KB Output is correct
70 Correct 9245 ms 121960 KB Output is correct