Submission #152437

#	Time	Username	Problem	Language	Result	Execution time	Memory
152437		arnold518	Sushi (JOI16_sushi)	C++14	100 / 100	11431 ms	144352 KiB

sushi

#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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80