Submission #1198041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198041		JooDdae	Sushi (JOI16_sushi)	C++20	100 / 100	9816 ms	152276 KiB

sushi

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

template<class T = int, class O = less<T>>
struct heap_set {
    priority_queue<T, vector<T>, O> pq, rpq;
    const T& top() const { return pq.top(); }
    int size() const { return int(pq.size() - rpq.size()); }
    bool empty() const { return !size(); }
    void flush() { while(rpq.size() && pq.top() == rpq.top()) pq.pop(), rpq.pop(); }
    void insert(const T x) { pq.push(x); flush(); }
    void pop() { pq.pop(); flush(); }
    void erase(const T x) { rpq.push(x); flush(); }
};

const int B = 10;

int n, m, a[400400];
heap_set<int> mx[808];
priority_queue<int, vector<int>, greater<>> pq[808], rpq[808];

void update_block(int u) {
    if(pq[u].empty()) return;

    for(int i=(u << B);i<min(n, (u+1 << B));i++) if(a[i] > pq[u].top()) {
        while(!rpq[u].empty() && !pq[u].empty() && rpq[u].top() == pq[u].top()) rpq[u].pop(), pq[u].pop();
        pq[u].push(a[i]), a[i] = pq[u].top(), pq[u].pop();
    }
    while(!pq[u].empty()) {
        int x = pq[u].top(); pq[u].pop();
        if(!rpq[u].empty() && x == rpq[u].top()) rpq[u].pop();
        else mx[u].erase(x);
    }
}

int update(int l, int r, int z) {
    int lb = l >> B, rb = r >> B;
    update_block(lb), update_block(rb);

    int L = (lb+1 << B);
    for(int i=l;i<=min(r, L-1);i++) if(a[i] > z) {
        mx[lb].erase(a[i]);
        swap(a[i], z);
        mx[lb].insert(a[i]);
    }
    if(r < L) return z;

    for(int i=lb+1;i<rb;i++) if(z < mx[i].top()) {
        int u = mx[i].top(); mx[i].pop();
        rpq[i].push(u), pq[i].push(z), mx[i].insert(z), z = u;
    }

    for(int i=(rb << B);i<=r;i++) if(a[i] > z) {
        mx[rb].erase(a[i]);
        swap(a[i], z);
        mx[rb].insert(a[i]);
    }
    
    return z;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) mx[i >> B].insert(a[i]);

    while(m--) {
        int l, r, z; cin >> l >> r >> z; l--, r--;
        cout << (r < l ? update(0, r, update(l, n-1, z)) : update(l, r, z)) << "\n";
    }
}

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