Submission #1212235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212235		stefanneagu	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	2098 ms	120660 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

const int nmax = 5e5 + 1, inf = 1e9;

int sz;
int n;

struct lenes {
    int aint[nmax * 8];
    int lz[nmax * 8];

    void reset() {
        for (int i = 1; i <= sz * 4; i++) {
            aint[i] = lz[i] = -inf;
        }
    }

    void prop(int nod, int st, int dr) {
        if (lz[nod] == -inf) {
            return;
        }
        aint[nod] = max(aint[nod], lz[nod]);
        if (st != dr) {
            lz[nod * 2] = max(lz[nod * 2], lz[nod]);
            lz[nod * 2 + 1] = max(lz[nod * 2 + 1], lz[nod]);
        }
        lz[nod] = -inf;
    }

    void hub(int nod, int st, int dr) {
        prop(nod, st, dr);
        if (st == dr) {
            return;
        }
        int mid = (st + dr) / 2;
        prop(nod * 2, st, mid);
        prop(nod * 2 + 1, mid + 1, dr);
    }

    void upd(int l, int r, int val, int nod = 1, int st = 1, int dr = sz) {
        prop(nod, st, dr);
        if (dr < l || r < st) return;
        if (l <= st && dr <= r) {
            lz[nod] = max(lz[nod], val);
            prop(nod, st, dr);
            return;
        }
        int mid = (st + dr) / 2;
        upd(l, r, val, nod * 2, st, mid);
        upd(l, r, val, nod * 2 + 1, mid + 1, dr);
        aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
    }

    int qry(int l, int r, int nod = 1, int st = 1, int dr = sz) {
        prop(nod, st, dr);
        if (dr < l || r < st) return -inf;
        if (l <= st && dr <= r) return aint[nod];
        int mid = (st + dr) / 2;
        int ans = max(qry(l, r, nod * 2, st, mid), qry(l, r, nod * 2 + 1, mid + 1, dr));
        return ans;
    }
} ds;

struct nu_lenes {
    int aint[nmax * 4];

    void upd(int i, int val, int nod = 1, int st = 1, int dr = n) {
        if (st == dr) {
            aint[nod] = val;
            return;
        }
        int mid = (st + dr) / 2;
        if (i <= mid) {
            upd(i, val, nod * 2, st, mid);
        } else {
            upd(i, val, nod * 2 + 1, mid + 1, dr);
        }
        aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
    }

    int qry(int l, int r, int nod = 1, int st = 1, int dr = n) {
        if (dr < l || r < st) return 0;
        if (l <= st && dr <= r) return aint[nod];
        int mid = (st + dr) / 2;
        return max(qry(l, r, nod * 2, st, mid), qry(l, r, nod * 2 + 1, mid + 1, dr));
    }
} swp;

struct str {
    int a, b;
} v[nmax], ind[nmax];

vector<pair<int, int>> qrys[nmax];
vector<int> scot[nmax];
int rasp[nmax];

void norm() {
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        mp[v[i].a], mp[v[i].b];
    }
    for (auto &it : mp) {
        it.second = ++sz;
    }
    for (int i = 1; i <= n; i++) {
        v[i].a = mp[v[i].a];
        v[i].b = mp[v[i].b];
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].b;
    }
    for (int i = 1; i <= n; i++) {
        cin >> v[i].a;
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        qrys[a].push_back({b, i});
    }
    norm();
    ds.reset();
    for (int i = 1; i <= n; i++) {
        ind[i].a = ds.qry(v[i].a, v[i].b);
        if (ind[i].a == -inf) {
            ind[i].a = 0;
        }
        ds.upd(v[i].a, v[i].b, i);
        scot[ind[i].a].push_back(i);
    }
    ds.reset();
    for (int i = n; i >= 1; i--) {
        ind[i].b = ds.qry(v[i].a, v[i].b);
        if (ind[i].b == -inf) {
            ind[i].b = n + 1;
        } else {
            ind[i].b = -ind[i].b;
        }
        ds.upd(v[i].a, v[i].b, -i);
    }
    for (int i = n; i >= 1; i--) {
        swp.upd(i, ind[i].b);
        for (auto it : scot[i]) {
            swp.upd(it, 0);
        }
        for (auto [j, qi] : qrys[i]) {
            rasp[qi] = (swp.qry(i, j) <= j);
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << (rasp[i] ? "Yes\n" : "No\n");
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 12 / 12