Submission #856672

# Submission time Handle Problem Language Result Execution time Memory
856672 2023-10-04T09:13:48 Z overwatch9 Sails (IOI07_sails) C++17
0 / 100
1000 ms 7260 KB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int maxn = 1e5;
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <int> tree;
    stree (int sz) {
        tree = vector <int> (sz*4);
    }
    void pushup(int v) {
        if (tree[lc] == 0)
            tree[v] = tree[rc];
        else
            tree[v] = tree[lc];
    }
    void update(int v, int tl, int tr, int p, int val) {
        if (tl > p || tr < p)
            return;
        if (tl == tr) {
            tree[v] += val;
            return;
        }
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, p, val);
        update(rc, tm+1, tr, p, val);
        pushup(v);
    }
    int query(int v, int tl, int tr, int p) {
        if (tl > p || tr < p)
            return 0;
        if (tl == tr)
            return tree[v];
        int tm = (tl + tr) / 2;
        int a = query(lc, tl, tm, p);
        if (a == 0)
            return query(rc, tm+1, tr, p);
        return 0;
    }
    // find index of leftmost value in the range l->r that is non zero
    int queryl(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l)
            return 0;
        if (tl == tr)
            return tree[v];
        int tm = (tl + tr) / 2;
        if (tl == tm && tm >= l) {
            if (tree[lc] != 0)
                return tl;
            return 0;
        }
        int a = queryl(lc, tl, tm, l, r);
        if (a != 0)
            return a;
        if (tm+1 == tr && tr <= r) {
            if (tree[rc] != 0)
                return tr;
            return 0;
        }
        a = queryl(rc, tm+1, tr, l, r);
        if (a != 0)
            return a;
        return 0;
    }
    // find index of rightmost value in the range l->r that is non zero
    int queryr(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l)
            return 0;
        int tm = (tl + tr) / 2;
        if (tm+1 == tr && tm+1 <= r) {
            if (tree[rc] != 0)
                return tr;
            return 0;
        }
        int a = queryr(rc, tm+1, tr, l, r);
        if (a != 0)
            return a;
        if (tl == tm && tm >= l) {
            if (tree[lc] != 0)
                return tl;
            return 0;
        }
        a = queryr(lc, tl, tm, l, r);
        if (a != 0)
            return a;
        return 0;
    }
};
struct node {
    int val = 0, pd = 0;
    bool up = false;
};
struct stree2 {
    #define lc v*2
    #define rc v*2+1
    vector <node> tree;
    stree2 (int sz) {
        tree = vector <node> (sz*4);
    }
    void pushup(int v) {
        tree[v].val = tree[lc].val + tree[rc].val;
    }
    void pushdown(int v, int tl, int tm, int tr) {
        if (!tree[v].up)
            return;
        tree[v].up = false;
        tree[lc].up = tree[rc].up = true;
        tree[lc].pd += tree[v].pd;
        tree[rc].pd += tree[v].pd;
        tree[lc].val += (tm - tl + 1);
        tree[rc].val += (tr - tm);
        tree[v].pd = 0;
    }
    void update(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l || l > r)
            return;
        if (tl >= l && tr <= r) {
            tree[v].pd++;
            tree[v].up = true;
            tree[v].val += (tr - tl + 1);
            return;
        }
        int tm = (tl + tr) / 2;
        pushdown(v, tl, tm, tr);
        update(lc, tl, tm, l, r);
        update(rc, tm+1, tr, l, r);
        pushup(v);
    }
    int query(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l)
            return 0;
        if (tl >= l && tr <= r)
            return tree[v].val;
        int tm = (tl + tr) / 2;
        pushdown(v, tl, tm, tr);
        int a = query(lc, tl, tm,l, r);
        int b = query(rc, tm+1, tr,l, r);
        return a + b;
    }
};
int main() {
    int n;
    cin >> n;
    vector <pair <int, int>> updates(n);
    for (int i = 0; i < n; i++)
        cin >> updates[i].first >> updates[i].second;
    sort(updates.begin(), updates.end());
    stree tree(maxn + 5);
    stree2 tree2(maxn + 5);
    int r = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        r = max(r, updates[i].first + 1);
        int k = updates[i].second;
        int v = tree.query(1, 0, maxn + 4, r - k - 1);
        ll res = tree2.query(1, 0, maxn + 4, r - k-1, r-2);
        ans += res;
        if (k == r) {
            tree.update(1, 0, maxn + 4, 0, 1);
            tree2.update(1, 0, maxn + 4, 0, r-2);
        } else if (v == 0) {
            int lb = tree.queryr(1, 0, maxn + 4, 0, r - k - 1);
            int rb = r-2;
            int lx = tree.queryl(1, 0, maxn + 4, r - k, rb);
            int rx = lx-1;
            if (lx == 0)
                rx = lb + k - 1;
            tree.update(1, 0, maxn + 4, lb, 1);
            tree.update(1, 0, maxn + 4, rx+1, -1);
            if (lx > 0)
                tree.update(1, 0, maxn + 4, lx, 1);

            tree2.update(1, 0, maxn + 4, lb, rx);
            if (lx > 0)
                tree2.update(1, 0, maxn + 4, lx, rb);
            
        } else {
            int lb = tree.queryr(1, 0, maxn + 4, 0, r - k - 1);
            int rb = r-2;

            tree.update(1, 0, maxn + 4, lb, 1);
            tree2.update(1, 0, maxn + 4, lb, rb);
        }
    }
    cout << ans << '\n';
}
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1026 ms 6992 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 7248 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 7252 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 7260 KB Time limit exceeded
2 Halted 0 ms 0 KB -