Submission #127273

#	Time	Username	Problem	Language	Result	Execution time	Memory
127273		choikiwon	Sushi (JOI16_sushi)	C++17	0 / 100	711 ms	17156 KiB

sushi

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

const int MN = 100010;
const int SQ = 2;
const int BS = (MN + SQ - 1) / SQ;

int N, Q;
int A[MN];

struct Query {
    int s, e, p;
};
Query query[MN];
multiset<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++) {
        auto it = V[bid].lower_bound(A[i]);
        if(it == V[bid].begin()) continue;
        int x = *(--it);
        V[bid].insert(A[i]);
        A[i] = x;
        V[bid].erase(V[bid].find(x));
    }

    V[bid].clear();
    X[bid].clear();
    for(int i = l; i <= r; i++) X[bid].insert(A[i]);
}

int proc1(int s, int e, int p) {
    int bid = s / SQ;
    prop(bid);

    X[bid].insert(p);
    for(int i = s; i <= e; i++) if(A[i] > p) swap(A[i], p);
    X[bid].erase(X[bid].find(p));
    return p;
}
int proc2(int bid, int v) {
    V[bid].insert(v);
    X[bid].insert(v);
    int mx = *X[bid].rbegin();
    X[bid].erase(X[bid].find(mx));
    return mx;
}

int solve(int s, int e, int p) {
    if(s / SQ == e / SQ) {
        return proc1(s, e, p);
    }
    else {
        p = proc1(s, (s / SQ + 1) * SQ - 1, p);
        for(int i = s / SQ + 1; i < e / SQ; i++) p = proc2(i, p);
        p = proc1(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 < Q; i++) {
        int s, e, p; scanf("%d %d %d", &s, &e, &p);
        s--; e--;
        query[i] = {s, e, p};
    }

    for(int i = 0; i < N; i++) {
        X[i / SQ].insert(A[i]);
    }
    for(int i = 0; i < Q; i++) {
        int s = query[i].s;
        int e = query[i].e;
        int p = query[i].p;

        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:65: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:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
sushi.cpp:72: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: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80