oj.uz

Submission #485642

# Submission time Handle Problem Language Result Execution time Memory
485642 2021-11-08T18:14:39 Z tibinyte Cambridge (info1cup18_cambridge) C++14
100 / 100
 549 ms 19548 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 447 ms 17492 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 43 ms 1996 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 13 ms 972 KB Output is correct
4 Correct 25 ms 1640 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 447 ms 17492 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 43 ms 1996 KB Output is correct
6 Correct 13 ms 972 KB Output is correct
7 Correct 25 ms 1640 KB Output is correct
8 Correct 549 ms 18904 KB Output is correct
9 Correct 489 ms 19032 KB Output is correct
10 Correct 493 ms 19036 KB Output is correct
11 Correct 443 ms 19548 KB Output is correct
12 Correct 537 ms 19028 KB Output is correct
13 Correct 3 ms 460 KB Output is correct