Submission #127229

#	Time	Username	Problem	Language	Result	Execution time	Memory
127229		choikiwon	Sushi (JOI16_sushi)	C++17	5 / 100	1176 ms	4100 KiB

sushi

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

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

int N, Q;
int A[MN];

struct Query {
    int s, e, p;
};
Query query[MN];

int Xn;
vector<int> X;
unordered_map<int, int> dx;

struct Fenwick {
    int n;
    vector<int> tree;
    void init(int n_) {
        n = n_;
        tree = vector<int>(n + 1, 0);
    }
    void upd(int x, int v) {
        for(int i = x + 1; i <= n; i += (i & -i)) tree[i] += v;
    }
    int quer(int a) {
        if(a >= n) a = n - 1;
        int ret = 0;
        for(int i = a + 1; i >= 1; i -= (i & -i)) ret += tree[i];
        return ret;
    }
    int quer(int a, int b) {
        return quer(b) - quer(a - 1);
    }
};

Fenwick fw[BS], tmp;
vector<int> V[BS];
int S[MN], E[MN], P[MN];

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

    vector<int> L;
    for(int i = l; i <= r; i++) {
        int s = 0, e = A[i], p = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            int t = tmp.quer(m, Xn - 1);
            if(t >= fw[bid].quer(m - 1)) {
                p = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        tmp.upd(A[i], 1);
        L.push_back(A[i]);
        A[i] = p;
    }

    for(int i = 0; i < L.size(); i++) {
        tmp.upd(L[i], -1);
    }
    for(int i = 0; i < V[bid].size(); i++) {
        fw[bid].upd(V[bid][i], -1);
    }
    V[bid].clear();
}

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

    for(int i = s; i <= e; i++) if(A[i] > p) swap(A[i], p);
    return p;
}
int proc2(int bid, int v) {
    int l = bid * SQ;
    int r = min(N - 1, l + SQ - 1);
    fw[bid].upd(v, 1);
    V[bid].push_back(v);

    int s = v + 1, e = Xn - 1, p = v;
    while(s <= e) {
        int m = (s + e)>>1;

        int cnt = 0;
        for(int i = l; i <= r; i++) if(A[i] >= m) cnt++;

        if(fw[bid].quer(m - 1) <= cnt) {
            p = m;
            s = m + 1;
        }
        else e = m - 1;
    }
    return p;
}

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]);
        X.push_back(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};
        X.push_back(p);
    }

    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());
    Xn = X.size();
    for(int i = 0; i < Xn; i++) dx[X[i]] = i;
    for(int i = 0; i < N; i++) {
        A[i] = dx[A[i]];
    }
    for(int i = 0; i < Q; i++) {
        query[i].p = dx[query[i].p];
    }

    for(int i = 0; i < BS; i++) {
        fw[i].init(Xn);
    }
    tmp.init(Xn);

    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", X[ solve(s, e, p) ]);
        }
        else {
            p = solve(s, N - 1, p);
            printf("%d\n", X[ solve(0, e, p) ]);
        }
    }

}

Compilation message (stderr)

sushi.cpp: In function 'void prop(int)':
sushi.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < L.size(); i++) {
                    ~~^~~~~~~~~~
sushi.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V[bid].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
sushi.cpp: In function 'int main()':
sushi.cpp:120: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:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
sushi.cpp:128: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: 0 / 15
• Subtask 3: 0 / 80