Submission #485642

#	Time	Username	Problem	Language	Result	Execution time	Memory
485642		tibinyte	Cambridge (info1cup18_cambridge)	C++14	100 / 100	549 ms	19548 KiB

cambridge

#include<bits/stdc++.h>
#define mod 1000000007
#define inf 1e14
using namespace std;
struct aint {
    vector<long long> a;
    vector<long long> lazy;
    void prop(int node, int left, int right) {
        a[node] += lazy[node];
        if (left != right) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void build(vector<long long>& b, int node, int left, int right) {
        if ((int)a.size() == 0) {
            int n = b.size() - 1;
            a = vector<long long>(4 * n);
            lazy = vector<long long>(4 * n);
        }
        if (left == right) {
            a[node] = b[left];
        }
        else {
            int mid = (left + right) / 2;
            build(b, 2 * node, left, mid);
            build(b, 2 * node + 1, mid + 1, right);
            a[node] = min(a[2 * node], a[2 * node + 1]);
        }
    }
    long long query(int node, int left, int right, int st, int dr) {
        if (left > right) {
            return inf;
        }
        prop(node, left, right);
        if (st <= left && dr >= right) {
            return a[node];
        }
        if ((st<left || st>right) && (dr<left || dr>right)) {
            return inf;
        }
        int mid = (left + right) / 2;
        return min(query(2 * node, left, mid, st, dr), query(2 * node + 1, mid + 1, right, st, dr));
    }
    void update(int node, int left, int right, int st, int dr, long long val) {
        if (left > right) {
            return;
        }
        prop(node, left, right);
        if (st <= left && dr >= right) {
            lazy[node] += val;
            return;
        }
        if ((st<left || st>right) && (dr<left || dr>right)) {
            return;
        }
        int mid = (left + right) / 2;
        update(2 * node, left, mid, st, dr, val);
        update(2 * node + 1, mid + 1, right, st, dr, val);
        prop(2 * node, left, mid);
        prop(2 * node + 1, mid + 1, right);
        a[node] = min(a[2 * node], a[2 * node + 1]);
    }
};
struct idiot {
    pair<int, int> val;
    int ind;
    bool operator <(idiot a)const {
        return (val < a.val || (val == a.val && ind < a.ind));
    }
};
vector<pair<int , int>> a;
map<idiot, int> poz;
int n, q;
aint tree;
void add(int ind) {
    int wh = poz[{a[ind], ind}];
    tree.update(1, 1, n, wh, wh, -inf + a[ind].first);
    tree.update(1, 1, n, wh, n, -a[ind].second);
}
void rem(int ind) {
    int wh = poz[{a[ind], ind}];
    tree.update(1, 1, n, wh, wh, inf - a[ind].first);
    tree.update(1, 1, n, wh, n, a[ind].second);
}
int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    a = vector<pair<int, int>>(n + 1);
    vector<idiot> norm(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].second >> a[i].first;
        norm[i].val = a[i];
        norm[i].ind = i;
    }
    sort(norm.begin() + 1, norm.end());
    for (int i = 1; i <= n; ++i) {
        poz[norm[i]] = i;
    }
    vector<long long> values(n + 1);
    for (int i = 1; i <= n; ++i) {
        values[i] = inf;
    }
    tree.build(values, 1, 1, n);
    int p = 1;
    vector<int> right(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (i > 1) {
            rem(i - 1);
        }
        if (p == i - 1) {
            p++;
        }
        while (p <= n) {
            add(p);
            if (tree.query(1, 1, n, 1, n) <= 0) {
                rem(p);
                break;
            }
            p++;
        }
        right[i] = p - 1;
    }
    while (q--) {
        int st, dr;
        cin >> st >> dr;
        if (right[st] < dr) {
            cout << 0 << '\n';
        }
        else {
            cout << 1 << '\n';
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 15 / 15
• Subtask 4: 45 / 45