Submission #127423

#	Time	Username	Problem	Language	Result	Execution time	Memory
127423		choikiwon	Sushi (JOI16_sushi)	C++17	100 / 100	8960 ms	100212 KiB

sushi

#include<bits/stdc++.h>
using namespace std;

const int MN = 400010;
const int SQ = 500;
const int BS = (MN + SQ - 1) / SQ;

int N, Q;
int A[MN];
priority_queue<int> V[BS], X[BS];

void prop(int bid) {
    int l = bid * SQ;
    int r = min(N - 1, l + SQ - 1);

    for(int i = l; i <= r; i++) {
        if(V[bid].empty() || -V[bid].top() >= A[i]) continue;
        V[bid].push(-A[i]);
        A[i] = -V[bid].top(); V[bid].pop();
    }

    while(!V[bid].empty()) V[bid].pop();
    while(!X[bid].empty()) X[bid].pop();
}

int go1(int s, int e, int p) {
    int bid = s / SQ;
    int l = bid * SQ;
    int r = min(N - 1, l + SQ - 1);
    prop(bid);

    for(int i = s; i <= e; i++) if(A[i] > p) swap(A[i], p);
    for(int i = l; i <= r; i++) X[bid].push(A[i]);
    return p;
}
int go2(int bid, int p) {
    V[bid].push(-p);
    X[bid].push(p);
    int mx = X[bid].top(); X[bid].pop();
    return mx;
}

int solve(int s, int e, int p) {
    if(s / SQ == e / SQ) {
        return go1(s, e, p);
    }
    else {
        p = go1(s, (s / SQ + 1) * SQ - 1, p);
        for(int i = s / SQ + 1; i < e / SQ; i++) p = go2(i, p);
        p = go1(e / SQ * SQ, e, p);
        return p;
    }
}

int main() {
    scanf("%d %d", &N, &Q);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    for(int i = 0; i < N; i++) {
        X[i / SQ].push(A[i]);
    }
    for(int i = 0; i < Q; i++) {
        int s, e, p; scanf("%d %d %d", &s, &e, &p);
        s--; e--;

        if(s <= e) {
            printf("%d\n", solve(s, e, p));
        }
        else {
            p = solve(s, N - 1, p);
            printf("%d\n", solve(0, e, p));
        }
    }
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:56: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:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
sushi.cpp:66:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int s, e, p; scanf("%d %d %d", &s, &e, &p);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80