oj.uz

Submission #152429

# Submission time Handle Problem Language Result Execution time Memory
152429 2019-09-08T02:10:59 Z arnold518 Sushi (JOI16_sushi) C++14
100 / 100
 11661 ms 125152 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=500;

    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 362 ms 25464 KB Output is correct
2 Correct 360 ms 25720 KB Output is correct
3 Correct 369 ms 25628 KB Output is correct
4 Correct 319 ms 25724 KB Output is correct
5 Correct 358 ms 25464 KB Output is correct
6 Correct 362 ms 25472 KB Output is correct
7 Correct 238 ms 25468 KB Output is correct
8 Correct 217 ms 25564 KB Output is correct
9 Correct 362 ms 25624 KB Output is correct
10 Correct 360 ms 25540 KB Output is correct
11 Correct 354 ms 25660 KB Output is correct
12 Correct 322 ms 25464 KB Output is correct
13 Correct 372 ms 25592 KB Output is correct
14 Correct 497 ms 25756 KB Output is correct
15 Correct 490 ms 25604 KB Output is correct
16 Correct 162 ms 25720 KB Output is correct
17 Correct 25 ms 25340 KB Output is correct
18 Correct 25 ms 25336 KB Output is correct
19 Correct 25 ms 25336 KB Output is correct
20 Correct 24 ms 25336 KB Output is correct
21 Correct 25 ms 25336 KB Output is correct
22 Correct 25 ms 25336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7237 ms 125012 KB Output is correct
2 Correct 7260 ms 123528 KB Output is correct
3 Correct 3880 ms 121528 KB Output is correct
4 Correct 7209 ms 125120 KB Output is correct
5 Correct 4774 ms 124988 KB Output is correct
6 Correct 7343 ms 125060 KB Output is correct
7 Correct 7276 ms 124952 KB Output is correct
8 Correct 7272 ms 124900 KB Output is correct
9 Correct 3526 ms 121516 KB Output is correct
10 Correct 4757 ms 123584 KB Output is correct
11 Correct 3491 ms 121464 KB Output is correct
12 Correct 6375 ms 123492 KB Output is correct
13 Correct 7156 ms 124904 KB Output is correct
14 Correct 7188 ms 123804 KB Output is correct
15 Correct 2752 ms 121464 KB Output is correct
16 Correct 7169 ms 124960 KB Output is correct
17 Correct 6447 ms 124860 KB Output is correct
18 Correct 7344 ms 124912 KB Output is correct
19 Correct 7279 ms 125152 KB Output is correct
20 Correct 5575 ms 125120 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 25464 KB Output is correct
2 Correct 360 ms 25720 KB Output is correct
3 Correct 369 ms 25628 KB Output is correct
4 Correct 319 ms 25724 KB Output is correct
5 Correct 358 ms 25464 KB Output is correct
6 Correct 362 ms 25472 KB Output is correct
7 Correct 238 ms 25468 KB Output is correct
8 Correct 217 ms 25564 KB Output is correct
9 Correct 362 ms 25624 KB Output is correct
10 Correct 360 ms 25540 KB Output is correct
11 Correct 354 ms 25660 KB Output is correct
12 Correct 322 ms 25464 KB Output is correct
13 Correct 372 ms 25592 KB Output is correct
14 Correct 497 ms 25756 KB Output is correct
15 Correct 490 ms 25604 KB Output is correct
16 Correct 162 ms 25720 KB Output is correct
17 Correct 25 ms 25340 KB Output is correct
18 Correct 25 ms 25336 KB Output is correct
19 Correct 25 ms 25336 KB Output is correct
20 Correct 24 ms 25336 KB Output is correct
21 Correct 25 ms 25336 KB Output is correct
22 Correct 25 ms 25336 KB Output is correct
23 Correct 7237 ms 125012 KB Output is correct
24 Correct 7260 ms 123528 KB Output is correct
25 Correct 3880 ms 121528 KB Output is correct
26 Correct 7209 ms 125120 KB Output is correct
27 Correct 4774 ms 124988 KB Output is correct
28 Correct 7343 ms 125060 KB Output is correct
29 Correct 7276 ms 124952 KB Output is correct
30 Correct 7272 ms 124900 KB Output is correct
31 Correct 3526 ms 121516 KB Output is correct
32 Correct 4757 ms 123584 KB Output is correct
33 Correct 3491 ms 121464 KB Output is correct
34 Correct 6375 ms 123492 KB Output is correct
35 Correct 7156 ms 124904 KB Output is correct
36 Correct 7188 ms 123804 KB Output is correct
37 Correct 2752 ms 121464 KB Output is correct
38 Correct 7169 ms 124960 KB Output is correct
39 Correct 6447 ms 124860 KB Output is correct
40 Correct 7344 ms 124912 KB Output is correct
41 Correct 7279 ms 125152 KB Output is correct
42 Correct 5575 ms 125120 KB Output is correct
43 Correct 7873 ms 38088 KB Output is correct
44 Correct 7859 ms 38112 KB Output is correct
45 Correct 5430 ms 34544 KB Output is correct
46 Correct 7087 ms 38116 KB Output is correct
47 Correct 7831 ms 38044 KB Output is correct
48 Correct 8274 ms 38196 KB Output is correct
49 Correct 8559 ms 38044 KB Output is correct
50 Correct 7627 ms 37448 KB Output is correct
51 Correct 8495 ms 37016 KB Output is correct
52 Correct 11319 ms 47032 KB Output is correct
53 Correct 10937 ms 46688 KB Output is correct
54 Correct 9604 ms 46832 KB Output is correct
55 Correct 11661 ms 46652 KB Output is correct
56 Correct 11523 ms 46784 KB Output is correct
57 Correct 11534 ms 46888 KB Output is correct
58 Correct 6134 ms 40756 KB Output is correct
59 Correct 6272 ms 40752 KB Output is correct
60 Correct 6541 ms 125068 KB Output is correct
61 Correct 7236 ms 125040 KB Output is correct
62 Correct 7211 ms 124932 KB Output is correct
63 Correct 7224 ms 125024 KB Output is correct
64 Correct 4525 ms 34588 KB Output is correct
65 Correct 4829 ms 78596 KB Output is correct
66 Correct 4622 ms 78416 KB Output is correct
67 Correct 10506 ms 107412 KB Output is correct
68 Correct 11058 ms 107480 KB Output is correct
69 Correct 11031 ms 107392 KB Output is correct
70 Correct 9327 ms 107260 KB Output is correct