Submission #1076279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076279		someone	Gift Exchange (JOI24_ho_t4)	C++14	100 / 100	860 ms	85588 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define sz(x) (int)x.size()
using namespace std;

const int M = 1 << 19, N = 2 * M, INF = 1e18 + 42, MOD = 998244353;

struct Inter {
    int l, r, i;

    bool operator <(const Inter& other) const {
        if(l == other.l) {
            if(r == other.r)
                return i < other.i;
            return r < other.r;
        }
        return l < other.l;
    }
};

Inter inter[M];
vector<int> id[M];
int n, q, lft[M], deb[M], ans[M], mini[N];

void pointUpd(int i, int val) {
    i += M;
    mini[i] = val;
    while(i >>= 1)
        mini[i] = min(mini[i*2], mini[i*2+1]);
}

int rmq(int l, int r) {
    int res = INF;
    l += M, r += M;
    while(l < r) {
        if(l & 1) res = min(res, mini[l++]);
        if(r & 1) res = min(res, mini[--r]);
        l >>= 1, r >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> inter[i].r;
        inter[i].r++;
        inter[i].i = i;
    }
    for(int i = 0; i < n; i++)
        cin >> inter[i].l;
    cin >> q;
    for(int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        l--, r--;
        deb[i] = l;
        id[r].push_back(i);
    }

    set<Inter> act;
    for(int i = n-1; i >= 0; i--) {
        auto it = act.lower_bound(inter[i]);
        while(it != act.end() && it->l < inter[i].r) {
            lft[it->i] = i;
            act.erase(it);
            it = act.lower_bound(inter[i]);
        }
        if(it != act.begin() && inter[i].l < (--it)->r) {
            lft[it->i] = i;
            act.erase(it);
        }
        act.insert(inter[i]);
    }
    for(Inter x : act) lft[x.i] = -INF;

    act.clear();
    for(int i = 0; i < n; i++) {
        auto it = act.lower_bound(inter[i]);
        while(it != act.end() && it->l < inter[i].r) {
            pointUpd(it->i, INF);
            act.erase(it);
            it = act.lower_bound(inter[i]);
        }
        if(it != act.begin() && inter[i].l < (--it)->r) {
            pointUpd(it->i, INF);
            act.erase(it);
        }
        act.insert(inter[i]);

        pointUpd(i, lft[i]);
        for(int iQ : id[i]) {
            ans[iQ] = (rmq(deb[iQ], i+1) >= deb[iQ]);
        }
    }
    for(int i = 0; i < q; i++)
        if(ans[i]) cout << "Yes\n";
        else cout << "No\n";
}

• 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