oj.uz

Submission #152424

# Submission time Handle Problem Language Result Execution time Memory
152424 2019-09-08T01:55:28 Z arnold518 Sushi (JOI16_sushi) C++14
20 / 100
 12000 ms 106964 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=sqrt(N);

    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 59 ms 25464 KB Output is correct
2 Correct 58 ms 25464 KB Output is correct
3 Correct 59 ms 25464 KB Output is correct
4 Correct 58 ms 25464 KB Output is correct
5 Correct 58 ms 25488 KB Output is correct
6 Correct 59 ms 25464 KB Output is correct
7 Correct 51 ms 25464 KB Output is correct
8 Correct 51 ms 25428 KB Output is correct
9 Correct 59 ms 25464 KB Output is correct
10 Correct 58 ms 25464 KB Output is correct
11 Correct 62 ms 25528 KB Output is correct
12 Correct 60 ms 25520 KB Output is correct
13 Correct 62 ms 25532 KB Output is correct
14 Correct 66 ms 25592 KB Output is correct
15 Correct 68 ms 25464 KB Output is correct
16 Correct 36 ms 25500 KB Output is correct
17 Correct 25 ms 25340 KB Output is correct
18 Correct 24 ms 25336 KB Output is correct
19 Correct 26 ms 25336 KB Output is correct
20 Correct 25 ms 25464 KB Output is correct
21 Correct 24 ms 25336 KB Output is correct
22 Correct 24 ms 25464 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7225 ms 106856 KB Output is correct
2 Correct 7259 ms 105360 KB Output is correct
3 Correct 4019 ms 103204 KB Output is correct
4 Correct 7163 ms 106932 KB Output is correct
5 Correct 6501 ms 106820 KB Output is correct
6 Correct 7262 ms 106960 KB Output is correct
7 Correct 7219 ms 106964 KB Output is correct
8 Correct 7198 ms 106804 KB Output is correct
9 Correct 3567 ms 103192 KB Output is correct
10 Correct 6372 ms 105320 KB Output is correct
11 Correct 3587 ms 103320 KB Output is correct
12 Correct 6408 ms 105432 KB Output is correct
13 Correct 7168 ms 106728 KB Output is correct
14 Correct 7249 ms 105244 KB Output is correct
15 Correct 4049 ms 103316 KB Output is correct
16 Correct 7212 ms 106848 KB Output is correct
17 Correct 6468 ms 106700 KB Output is correct
18 Correct 7209 ms 106788 KB Output is correct
19 Correct 7208 ms 106880 KB Output is correct
20 Correct 7153 ms 106808 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 25464 KB Output is correct
2 Correct 58 ms 25464 KB Output is correct
3 Correct 59 ms 25464 KB Output is correct
4 Correct 58 ms 25464 KB Output is correct
5 Correct 58 ms 25488 KB Output is correct
6 Correct 59 ms 25464 KB Output is correct
7 Correct 51 ms 25464 KB Output is correct
8 Correct 51 ms 25428 KB Output is correct
9 Correct 59 ms 25464 KB Output is correct
10 Correct 58 ms 25464 KB Output is correct
11 Correct 62 ms 25528 KB Output is correct
12 Correct 60 ms 25520 KB Output is correct
13 Correct 62 ms 25532 KB Output is correct
14 Correct 66 ms 25592 KB Output is correct
15 Correct 68 ms 25464 KB Output is correct
16 Correct 36 ms 25500 KB Output is correct
17 Correct 25 ms 25340 KB Output is correct
18 Correct 24 ms 25336 KB Output is correct
19 Correct 26 ms 25336 KB Output is correct
20 Correct 25 ms 25464 KB Output is correct
21 Correct 24 ms 25336 KB Output is correct
22 Correct 24 ms 25464 KB Output is correct
23 Correct 7225 ms 106856 KB Output is correct
24 Correct 7259 ms 105360 KB Output is correct
25 Correct 4019 ms 103204 KB Output is correct
26 Correct 7163 ms 106932 KB Output is correct
27 Correct 6501 ms 106820 KB Output is correct
28 Correct 7262 ms 106960 KB Output is correct
29 Correct 7219 ms 106964 KB Output is correct
30 Correct 7198 ms 106804 KB Output is correct
31 Correct 3567 ms 103192 KB Output is correct
32 Correct 6372 ms 105320 KB Output is correct
33 Correct 3587 ms 103320 KB Output is correct
34 Correct 6408 ms 105432 KB Output is correct
35 Correct 7168 ms 106728 KB Output is correct
36 Correct 7249 ms 105244 KB Output is correct
37 Correct 4049 ms 103316 KB Output is correct
38 Correct 7212 ms 106848 KB Output is correct
39 Correct 6468 ms 106700 KB Output is correct
40 Correct 7209 ms 106788 KB Output is correct
41 Correct 7208 ms 106880 KB Output is correct
42 Correct 7153 ms 106808 KB Output is correct
43 Correct 9018 ms 37424 KB Output is correct
44 Correct 9018 ms 37300 KB Output is correct
45 Correct 6254 ms 33980 KB Output is correct
46 Correct 9008 ms 37336 KB Output is correct
47 Correct 9016 ms 37456 KB Output is correct
48 Correct 9421 ms 37548 KB Output is correct
49 Correct 9713 ms 37636 KB Output is correct
50 Correct 9772 ms 37424 KB Output is correct
51 Correct 9683 ms 37432 KB Output is correct
52 Execution timed out 12096 ms 44284 KB Time limit exceeded
53 Halted 0 ms 0 KB -