Submission #1220833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220833		duckindog	Sushi (JOI16_sushi)	C++20	100 / 100	1522 ms	78704 KiB

sushi

#include <bits/stdc++.h>

using namespace std;

const int N = 400'000 + 10,
            S = 632;
int n, q;
int a[N];

struct Block { 
    int st, ed;
    priority_queue<int> pq;
    vector<int> vt;

    void build() { 
        if (!vt.size()) return;
        priority_queue<int, vector<int>, greater<>> pq_(vt.begin(), vt.end());
        vt.clear();

        for (int i = st; i <= ed; ++i) { 
            if (a[i] > pq_.top()) { 
                pq_.push(a[i]);
                a[i] = pq_.top(); pq_.pop();
            }
        }
    }
    int miniModify(int l, int r, int x) { 
        build();
        for (int i = l; i <= r; ++i) { 
            if (a[i] > x) swap(a[i], x);
        }
        pq = priority_queue<int>(a + st, a + ed + 1);
        return x;
    }

    int push(int x) { 
        vt.push_back(x);
        if (pq.top() > x) { 
            pq.push(x);
            x = pq.top(); pq.pop();
        }
        return x;
    }
} B[N / S + 5];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int block = 1; block <= (n - 1) / S + 1; ++block) { 
        int l = block * S - S + 1, r = min(block * S, n);
        B[block].st = l; B[block].ed = r;
        B[block].pq = priority_queue<int>(a + l, a + r + 1);
    }

    auto cal = [&](int l, int r, int x) { 
        int blockL = (l - 1) / S + 1, blockR = (r - 1) / S + 1;
        if (blockL == blockR) { 
            return B[blockL].miniModify(l, r, x);
        } 
        int edL = blockL * S, stR = blockR * S - S + 1;
        x = B[blockL].miniModify(l, edL, x);
        for (int i = blockL + 1; i < blockR; ++i) x = B[i].push(x);
        x = B[blockR].miniModify(stR, r, x);
        return x;
    };

    while (q--) { 
        int l, r, x; cin >> l >> r >> x;

        if (l <= r) { 
            cout << cal(l, r, x) << "\n";
        } else { 
            cout << cal(1, r, cal(l, n, x)) << "\n";
        }
    }
}

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