oj.uz

Submission #152425

# Submission time Handle Problem Language Result Execution time Memory
152425 2019-09-08T02:01:31 Z arnold518 Sushi (JOI16_sushi) C++14
20 / 100
 12000 ms 99892 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=700;

    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 453 ms 25600 KB Output is correct
2 Correct 453 ms 25540 KB Output is correct
3 Correct 462 ms 25600 KB Output is correct
4 Correct 441 ms 25524 KB Output is correct
5 Correct 445 ms 25592 KB Output is correct
6 Correct 452 ms 25724 KB Output is correct
7 Correct 285 ms 25336 KB Output is correct
8 Correct 293 ms 25464 KB Output is correct
9 Correct 448 ms 25512 KB Output is correct
10 Correct 447 ms 25720 KB Output is correct
11 Correct 439 ms 25592 KB Output is correct
12 Correct 445 ms 25596 KB Output is correct
13 Correct 461 ms 25640 KB Output is correct
14 Correct 638 ms 25596 KB Output is correct
15 Correct 628 ms 25620 KB Output is correct
16 Correct 211 ms 25464 KB Output is correct
17 Correct 26 ms 25336 KB Output is correct
18 Correct 25 ms 25336 KB Output is correct
19 Correct 25 ms 25336 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 25336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6226 ms 99580 KB Output is correct
2 Correct 6145 ms 98212 KB Output is correct
3 Correct 3186 ms 96288 KB Output is correct
4 Correct 6101 ms 99768 KB Output is correct
5 Correct 5580 ms 99540 KB Output is correct
6 Correct 6219 ms 99892 KB Output is correct
7 Correct 6193 ms 99656 KB Output is correct
8 Correct 6186 ms 99504 KB Output is correct
9 Correct 2984 ms 96120 KB Output is correct
10 Correct 5482 ms 98196 KB Output is correct
11 Correct 2977 ms 96028 KB Output is correct
12 Correct 5451 ms 98248 KB Output is correct
13 Correct 6163 ms 99480 KB Output is correct
14 Correct 6156 ms 98188 KB Output is correct
15 Correct 3139 ms 96000 KB Output is correct
16 Correct 6136 ms 99572 KB Output is correct
17 Correct 5466 ms 99564 KB Output is correct
18 Correct 6266 ms 99556 KB Output is correct
19 Correct 6223 ms 99588 KB Output is correct
20 Correct 6159 ms 99520 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 25600 KB Output is correct
2 Correct 453 ms 25540 KB Output is correct
3 Correct 462 ms 25600 KB Output is correct
4 Correct 441 ms 25524 KB Output is correct
5 Correct 445 ms 25592 KB Output is correct
6 Correct 452 ms 25724 KB Output is correct
7 Correct 285 ms 25336 KB Output is correct
8 Correct 293 ms 25464 KB Output is correct
9 Correct 448 ms 25512 KB Output is correct
10 Correct 447 ms 25720 KB Output is correct
11 Correct 439 ms 25592 KB Output is correct
12 Correct 445 ms 25596 KB Output is correct
13 Correct 461 ms 25640 KB Output is correct
14 Correct 638 ms 25596 KB Output is correct
15 Correct 628 ms 25620 KB Output is correct
16 Correct 211 ms 25464 KB Output is correct
17 Correct 26 ms 25336 KB Output is correct
18 Correct 25 ms 25336 KB Output is correct
19 Correct 25 ms 25336 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 25336 KB Output is correct
23 Correct 6226 ms 99580 KB Output is correct
24 Correct 6145 ms 98212 KB Output is correct
25 Correct 3186 ms 96288 KB Output is correct
26 Correct 6101 ms 99768 KB Output is correct
27 Correct 5580 ms 99540 KB Output is correct
28 Correct 6219 ms 99892 KB Output is correct
29 Correct 6193 ms 99656 KB Output is correct
30 Correct 6186 ms 99504 KB Output is correct
31 Correct 2984 ms 96120 KB Output is correct
32 Correct 5482 ms 98196 KB Output is correct
33 Correct 2977 ms 96028 KB Output is correct
34 Correct 5451 ms 98248 KB Output is correct
35 Correct 6163 ms 99480 KB Output is correct
36 Correct 6156 ms 98188 KB Output is correct
37 Correct 3139 ms 96000 KB Output is correct
38 Correct 6136 ms 99572 KB Output is correct
39 Correct 5466 ms 99564 KB Output is correct
40 Correct 6266 ms 99556 KB Output is correct
41 Correct 6223 ms 99588 KB Output is correct
42 Correct 6159 ms 99520 KB Output is correct
43 Correct 9123 ms 36844 KB Output is correct
44 Correct 9093 ms 36736 KB Output is correct
45 Correct 6458 ms 33084 KB Output is correct
46 Correct 9099 ms 36740 KB Output is correct
47 Correct 9084 ms 36752 KB Output is correct
48 Correct 9521 ms 36804 KB Output is correct
49 Correct 9867 ms 36740 KB Output is correct
50 Correct 9835 ms 36416 KB Output is correct
51 Correct 9873 ms 36232 KB Output is correct
52 Correct 11815 ms 41856 KB Output is correct
53 Correct 11454 ms 41900 KB Output is correct
54 Correct 11802 ms 42136 KB Output is correct
55 Execution timed out 12063 ms 41944 KB Time limit exceeded
56 Halted 0 ms 0 KB -