Submission #1057599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057599		sammyuri	Gift Exchange (JOI24_ho_t4)	C++17	88 / 100	494 ms	40020 KiB

Main

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

/*
for each index, calculate val[i],
the minimum index j > i such that they intersect
note that it is valid iff for all l, l + 1, .. , r - 1
val[i] <= r
so use a max segtree?

for each index, calculate closest left and right that is required
then we get an invalid range L..R
so we have n invalid ranges
and for each query, we want to find if it is contained in any of these ranges
go from left to right
and do sweep line
maintain it with multiset
3 events
*/

const int MAXN = (1 << 19);
int LEFT[MAXN], RIGHT[MAXN];
int tree[2 * MAXN];
int lazy[2 * MAXN];


void init() {
    for (int i = 0; i < MAXN * 2; i ++)
        tree[i] = 1e9, lazy[i] = 1e9;
}
void pushdown(int index) {
    if (lazy[index] != 1e9) {
        tree[index] = min(tree[index], lazy[index]);
        if (index < MAXN) {
            lazy[2 * index] = min(lazy[2 * index], lazy[index]);
            lazy[2 * index + 1] = min(lazy[2 * index + 1], lazy[index]);
        }
        lazy[index] = 1e9;
    }
}
void upd(int left, int right, int index, int maxl, int maxr, int value) {
    // cout << left << " " << right << " " << index << " " << value << " " << maxl << " " << maxr << endl;
    pushdown(index);
    if (left == maxl && right == maxr) {
        lazy[index] = min(lazy[index], value); return;
    }
    int mid = (maxl + maxr) / 2;
    if (left <= mid) {
        upd(left, min(mid, right), 2 * index, maxl, mid, value);
    }
    if (right >= mid + 1) {
        upd(max(mid + 1, left), right, 2 * index + 1, mid + 1, maxr, value);
    }
    if (index < MAXN) {
        pushdown(2 * index); pushdown(2 * index + 1);
        tree[index] = min(tree[2 * index], tree[2 * index + 1]);
    }
}
void upd(int l, int r, int val) {upd(l, r, 1, 0, MAXN - 1, val);}
int query(int left, int right, int index, int maxl, int maxr) {
    pushdown(index);
    if (left == maxl && right == maxr)
        return tree[index];
    int ans = 1e9;
    int mid = (maxl + maxr) / 2;
    if (left <= mid) {
        ans = min(ans, query(left, min(mid, right), 2 * index, maxl, mid));
    }
    if (right >= mid + 1) {
        ans = min(ans, query(max(mid + 1, left), right, 2 * index + 1, mid + 1, maxr));
    }
    return ans;
}
int query(int l, int r) {return query(l, r, 1, 0, MAXN - 1);}


int tree2[2 * MAXN];
void init2() {
    for (int i = 0; i < 2 * MAXN; i ++)
        tree2[i] = 0;
}
void upd2(int index, int value) {
    index += MAXN;
    tree2[index] += value;
    index /= 2;
    while (index) {
        tree2[index] = tree2[2 * index] + tree2[2 * index + 1];
        index /= 2;
    }
}
int query2(int left, int right, int index, int maxl, int maxr) {
    if (left == maxl && right == maxr)
        return tree2[index];
    int ans = 0;
    int mid = (maxl + maxr) / 2;
    if (left <= mid) {
        ans += query2(left, min(mid, right), 2 * index, maxl, mid);
    }
    if (right >= mid + 1) {
        ans += query2(max(mid + 1, left), right, 2 * index + 1, mid + 1, maxr);
    }
    return ans;
}
int query2(int l, int r) {return query2(l, r, 1, 0, MAXN - 1);}

#define BAD_BEGIN 0
#define QUERY 2
#define BAD_END 1

struct event {
    int type;
    int pos;
    int index;
    event (int _t, int _p, int _i) {type = _t, pos = _p, index = _i;}
};
bool operator < (event a, event b) {
    if (a.pos != b.pos)
        return a.pos < b.pos;
    if (a.type != b.type)
        return a.type < b.type;
    return a.index < b.index;
}

int main() {
    int n; cin >> n;
    vector<int> aa(n), bb(n);
    for (auto &a : aa) cin >> a;
    for (auto &a : bb) cin >> a;
    // find initial values
    init();
    for (int i = n - 1; i >= 0; i --) {
        RIGHT[i] = query(bb[i], aa[i]);
        upd(bb[i], aa[i], i);
    }
    // cout << query(1, 5) << endl;
    init();
    for (int i = 0; i < n; i ++) {
        LEFT[i] = n - 1 - query(bb[i], aa[i]);
        if (LEFT[i] < 0)
            LEFT[i] = -1;
        upd(bb[i], aa[i], n - 1 - i);
    }
    
    // for (int i = 0; i < n; i ++)
    //     cout << LEFT[i] << " "; cout << endl;
    // for (int i = 0; i < n; i ++)
    //     cout << RIGHT[i] << " "; cout << endl;

    vector<event> events;
    // add events to list
    for (int i = 0; i < n; i ++) {
        events.push_back(event(BAD_BEGIN, LEFT[i] + 1, i));
        events.push_back(event(BAD_END, i + 1, i));
    }
    int q; cin >> q;
    vector<bool> ans(q);
    vector<int> rights(q);
    for (int i = 0; i < q; i ++) {
        int l, r; cin >> l >> r;
        l --; r --;
        rights[i] = r;
        events.push_back(event(QUERY, l, i));
    }
    sort(events.begin(), events.end());
    // sweep line
    init2();
    for (auto a : events) {
        // cout << a.pos << " " << a.type << " " << a.index << endl;
        if (a.type == BAD_BEGIN) {
            upd2(a.index, 1);
            if (RIGHT[a.index] < MAXN)
                upd2(RIGHT[a.index], -1);
        } else if (a.type == BAD_END) {
            upd2(a.index, -1);
            if (RIGHT[a.index] < MAXN)
                upd2(RIGHT[a.index], 1);
        } else {
            int r = rights[a.index];
            int xx = query2(0, r);
            // cout << xx << endl;
            if (xx)
                ans[a.index] = false;
            else ans[a.index] = true;
        }
    }
    for (auto a : ans)
        cout << (a ? "Yes" : "No") << endl;
    return 0;
}

/*
10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
1
2 9

5
3 4 6 9 10
1 2 5 7 8
1
1 2
*/

• 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: 0 / 12