Submission #1198007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198007		JooDdae	Sushi (JOI16_sushi)	C++20	0 / 100	12089 ms	111912 KiB

sushi

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

const int B = 9;

int n, m, a[400400];
multiset<int> mx[808];
priority_queue<int, vector<int>, greater<>> pq[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()) {
        mx[u].erase(mx[u].find(a[i]));
        pq[u].push(a[i]), a[i] = pq[u].top(), pq[u].pop();
        mx[u].insert(a[i]);
    }
    while(!pq[u].empty()) pq[u].pop();
}

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(mx[lb].find(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].rbegin()) {
        int u = *mx[i].rbegin();
        mx[i].erase(mx[i].find(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(mx[rb].find(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: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80