oj.uz

답안 #254334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254334 2020-07-29T21:14:58 Z aZvezda Sails (IOI07_sails) C++14
25 / 100
 349 ms 52388 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 = 4e5 + 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);
    }
}

ll firstEqual(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].mx >= val) {
        return firstEqual(curr * 2, l, m, val);
    } else {
        return firstEqual(curr * 2 + 1, m + 1, r, val);
    }
}

pair<ll, ll> arr[MAX_N];
ll n;
ll offset = 2e5 + 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, 0, MAX_N - 1, -mod);
    upd(1, 0, MAX_N - 1, offset, MAX_N - 1, 2 * mod);
    int last = offset;
    for(ll i = 0; i < n; i ++) {
        ll nowoff = offset - arr[i].first;
        while(last > nowoff) {
            last --;
            upd(1, 0, MAX_N - 1, last, last, mod);
        }
        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 = firstEqual(1, 0, MAX_N - 1, now), r = lastEqual(1, 0, MAX_N - 1, now);
        ll toChange = nowoff + arr[i].second - l;

        //cout << l << endl;
        /*
        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;
        */
        upd(1, 0, MAX_N - 1, nowoff, l - 1, 1);
        upd(1, 0, MAX_N - 1, r - toChange + 1, r, 1);
        //continue;


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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 50432 KB Output is correct
2 Correct 24 ms 50432 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 50432 KB Output is correct
2 Correct 28 ms 50436 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 50424 KB Output is correct
2 Correct 30 ms 50424 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 50488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 50468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 50672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 127 ms 51292 KB Output isn't correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 51576 KB Output isn't correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 280 ms 51992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 318 ms 52216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 349 ms 52388 KB Output isn't correct
2 Halted 0 ms 0 KB -