Submission #1299534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299534		shidou26	Sushi (JOI16_sushi)	C++20	100 / 100	1794 ms	61132 KiB

sushi

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

struct Query {
    int s, t, p;
};

const int N = 4e5 + 3;
const int S = 900;

int n, q;
int a[N];
Query query[N];

int block[N];
vector<int> low, up;
vector<priority_queue<int>> price;
vector<priority_queue<int, vector<int>, greater<int>>> tag;

void build(int b) {
    priority_queue<int>(a + low[b], a + up[b] + 1).swap(price[b]);
}

void apply_update(int b) {
    if(tag[b].empty()) return;
    for(int i = low[b]; i <= up[b]; i++) {
        if(tag[b].top() < a[i]) {
            tag[b].push(a[i]);
            a[i] = tag[b].top();
            tag[b].pop();
        }
    }
    priority_queue<int, vector<int>, greater<int>>().swap(tag[b]);
}

int modify(int l, int r, int p) {
    if(block[l] == block[r]) {
        apply_update(block[l]);
        for(int i = l; i <= r; i++) if(p < a[i]) swap(a[i], p);
        build(block[l]);
        return p;
    }
    
    apply_update(block[l]);
    for(int i = l; i <= up[block[l]]; i++) if(p < a[i]) swap(a[i], p);
    build(block[l]);

    for(int i = block[l] + 1; i < block[r]; i++) {
        if(p < price[i].top()) {
            tag[i].push(p);
            price[i].push(p);
            p = price[i].top();
            price[i].pop();
        }
    }
    
    apply_update(block[r]);
    for(int i = low[block[r]]; i <= r; i++) if(p < a[i]) swap(a[i], p);
    build(block[r]);

    return p;
}

int main() {
    scanf("%d%d", &n, &q);

    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    for(int i = 1; i <= q; i++) {
        scanf("%d%d%d", &query[i].s, &query[i].t, &query[i].p);
    }

    for(int i = 1; i <= n; i++) block[i] = (i - 1) / S + 1;

    low.resize(block[n] + 1);
    up.resize(block[n] + 1);
    price.resize(block[n] + 1);
    tag.resize(block[n] + 1);

    for(int i = 1; i <= block[n]; i++) {
        low[i] = (i - 1) * S + 1;
        up[i] = min(n, i * S);
        build(i);
    }

    for(int i = 1; i <= q; i++) {
        if(query[i].s <= query[i].t) cout << modify(query[i].s, query[i].t, query[i].p) << endl;
        else {
            int apply = modify(query[i].s, n, query[i].p);
            cout << modify(1, query[i].t, apply) << endl;
        }
    }

    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << endl;

    return 0;
}

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]
   65 |     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]
   68 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sushi.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d%d%d", &query[i].s, &query[i].t, &query[i].p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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