oj.uz

Submission #637333

# Submission time Handle Problem Language Result Execution time Memory
637333 2022-09-01T11:44:12 Z tvladm2009 Cambridge (info1cup18_cambridge) C++14
100 / 100
 415 ms 130508 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAX_N = 1e5;
const int lim = 1e9;
const ll INF = (1LL << 60);

int t[MAX_N + 1], d[MAX_N + 1];
int minLeft[MAX_N + 1];

int n, q;

struct Node {
    Node *lson;
    Node *rson;
    ll lazy;
    ll minVal;
    int cnt;

    Node() {
        lson = NULL;
        rson = NULL;
        lazy = 0;
        minVal = INF;
        cnt = 0;
    }
};

void push(Node *&root, int l, int r) {
    if (l == r) {
        return;
    }
    if (root->lson == NULL) {
        root->lson = new Node();
    }
    if (root->rson == NULL) {
        root->rson = new Node();
    }
    if (root->lazy != 0) {
        root->lson->lazy += root->lazy;
        root->lson->minVal += root->lazy;
        root->rson->lazy += root->lazy;
        root->rson->minVal += root->lazy;
        root->lazy = 0;
    }
}

void update(Node *&root, int l, int r, int p, int q, int val) {
    if (p > q) {
        return;
    } else if (p <= l && r <= q) {
        root->minVal += val;
        root->lazy += val;
    } else {
        push(root, l, r);
        int mid = (l + r) / 2;
        update(root->lson, l, mid, p, min(mid, q), val);
        update(root->rson, mid + 1, r, max(p, mid + 1), q, val);
        ll ql = INF, qr = INF;
        if (root->lson != NULL) {
            ql = root->lson->minVal;
        }
        if (root->rson != NULL) {
            qr = root->rson->minVal;
        }
        root->minVal = min(ql, qr);
    }
}

ll query(Node *&root, int l, int r) {
    push(root, l, r);
    return root->minVal;
}

void updateFreq(Node *&root, int l, int r, int x, int val) {
    push(root, l, r);
    if (l == r) {
        if (root->cnt == 0) {
            root->minVal -= INF - x;
        }
        root->cnt += val;
        if (root->cnt == 0) {
            root->minVal += INF - x;
        }
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        updateFreq(root->lson, l, mid, x, val);
    } else {
        updateFreq(root->rson, mid + 1, r, x, val);
    }
    ll ql = INF, qr = INF;
    if (root->lson != NULL) {
        ql = root->lson->minVal;
    }
    if (root->rson != NULL) {
        qr = root->rson->minVal;
    }
    root->minVal = min(ql, qr);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> d[i];
    }

    Node *root = new Node();
    int j = 1;
    for (int i = 1; i <= n; i++) {
        updateFreq(root, 1, lim, d[i], 1);
        update(root, 1, lim, d[i], lim, -t[i]);
        while (query(root, 1, lim) <= 0LL) {
            update(root, 1, lim, d[j], lim, t[j]);
            updateFreq(root, 1, lim, d[j], -1);
            j++;
        }
        minLeft[i] = j;
    }

    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << (x >= minLeft[y]) << "\n";
    }

    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 379 ms 129056 KB Output is correct
4 Correct 4 ms 2260 KB Output is correct
5 Correct 38 ms 16276 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 15 ms 2744 KB Output is correct
4 Correct 24 ms 3200 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 379 ms 129056 KB Output is correct
4 Correct 4 ms 2260 KB Output is correct
5 Correct 38 ms 16276 KB Output is correct
6 Correct 15 ms 2744 KB Output is correct
7 Correct 24 ms 3200 KB Output is correct
8 Correct 411 ms 121912 KB Output is correct
9 Correct 415 ms 130508 KB Output is correct
10 Correct 401 ms 130348 KB Output is correct
11 Correct 174 ms 4992 KB Output is correct
12 Correct 199 ms 4488 KB Output is correct
13 Correct 3 ms 980 KB Output is correct