oj.uz

Submission #254300

# Submission time Handle Problem Language Result Execution time Memory
254300 2020-07-29T19:57:56 Z aZvezda Sails (IOI07_sails) C++14
25 / 100
 291 ms 27996 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const ll MAX_N = 2e5 + 10;

struct Node {
    ll sum, mx, mn, lazy;
    Node() {sum = mx = mn = lazy = 0;}
};

Node tree[4 * MAX_N];

void push(ll curr, ll l, ll r) {
    tree[curr].sum += tree[curr].lazy * (r - l + 1);
    tree[curr].mx += tree[curr].lazy;
    tree[curr].mn += tree[curr].lazy;
    if(l != r) {
        tree[curr * 2].lazy += tree[curr].lazy;
        tree[curr * 2 + 1].lazy += tree[curr].lazy;
    }
    tree[curr].lazy = 0;
}

Node operator +(const Node &a, const Node &b) {
    Node ret;
    ret.sum = a.sum + b.sum;
    ret.mx = max(a.mx, b.mx);
    ret.mn = min(a.mn, b.mn);
    return ret;
}

void upd(ll curr, ll l, ll r, ll ql, ll qr, ll val) {
    push(curr, l, r);
    if(ql <= l && r <= qr) {
        tree[curr].lazy += val;
        push(curr, l, r);
        return;
    } else if(l > qr || r < ql) {return;}
    ll m = (l + r) / 2ll;
    upd(curr * 2, l, m, ql, qr, val);
    upd(curr * 2 + 1, m + 1, r, ql, qr, val);
    tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
}

ll sum(ll curr, ll l, ll r, ll ql, ll qr) {
    push(curr, l, r);
    if(ql <= l && r <= qr) {
        return tree[curr].sum;
    } else if(l > qr || r < ql) {return 0;}
    ll m = (l + r) / 2ll;
    return sum(curr * 2, l, m, ql, qr) + sum(curr * 2 + 1, m + 1, r, ql, qr);
}

ll lastEqual(ll curr, ll l, ll r, ll val) {
    push(curr, l, r);
    if(l == r) {
        return r;
    }
    ll m = (l + r) / 2ll;
    //cout << "Searching " << val << " " << curr << " " << l << " " << r << " " << tree[curr].mx << " " << tree[curr * 2].mx << endl;
    if(tree[curr * 2 + 1].mn > val) {
        return lastEqual(curr * 2, l, m, val);
    } else {
        return lastEqual(curr * 2 + 1, m + 1, r, val);
    }
}

pair<ll, ll> arr[MAX_N];
ll n;
ll offset = 1e5 + 10;

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(ll i = 0; i < n; i ++) {
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr, arr + n);
    ll ret = 0;
    upd(1, 0, MAX_N - 1, offset, MAX_N - 1, mod);
    for(ll i = 0; i < n; i ++) {
        ll nowoff = offset - arr[i].first;
        ll now = sum(1, 0, MAX_N - 1, nowoff + arr[i].second - 1, nowoff + arr[i].second - 1);
        ret += sum(1, 0, MAX_N - 1, nowoff, nowoff + arr[i].second - 1);

        ll l = max(lastEqual(1, 0, MAX_N - 1, now - 1) + 1, nowoff), r = min(lastEqual(1, 0, MAX_N - 1, now), nowoff + arr[i].first - 1);
        ll toChange = nowoff + arr[i].second - l;


        upd(1, 0, MAX_N - 1, nowoff, l - 1, 1);
        upd(1, 0, MAX_N - 1, r - toChange + 1, r, 1);
        continue;
        cout << l - nowoff << " " << r - nowoff << " " << nowoff + arr[i].second - nowoff << " " << now << " " << ret << " " << toChange << endl;
        cout << "Curr " << i << " " << arr[i].first << " " << arr[i].second << endl;
        for(ll j = nowoff; j < nowoff + arr[i].first; j ++) {
            cout << sum(1, 0, MAX_N - 1, j, j) << " ";
        }
        cout << endl << endl;

    }
    cout << ret << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25344 KB Output is correct
2 Correct 12 ms 25344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25344 KB Output is correct
2 Correct 13 ms 25252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25344 KB Output is correct
2 Correct 13 ms 25344 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 25344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 25472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 25512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 26104 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 26744 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 27456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 27868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 27996 KB Output isn't correct
2 Halted 0 ms 0 KB -