oj.uz

Submission #123640

# Submission time Handle Problem Language Result Execution time Memory
123640 2019-07-01T21:31:55 Z Osama_Alkhodairy Sails (IOI07_sails) C++17
100 / 100
 622 ms 4344 KB 
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 100001;

int n, tree[4 * N], lazy[4 * N];
int arr[N];
vector <pair <int, int> > a;

void shift(int l, int r, int node){
    if(r < l) return;
    if(lazy[node] == 0) return;
    tree[node] += (r - l + 1) * lazy[node];
    if(l != r){
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
}
void update(int l, int r, int node, int s, int e){
    if(r < l || r < s || l > e) return;
    shift(l, r, node);
    if(s <= l && r <= e){
        tree[node] += r - l + 1;
        if(l != r){
            lazy[2 * node]++;
            lazy[2 * node + 1]++;
        }
        return;
    }
    int mid = (l + r) / 2;
    update(l, mid, 2 * node, s, e);
    update(mid + 1, r, 2 * node + 1, s, e);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int query(int l, int r, int node, int idx){
    assert(l <= idx && idx <= r);
    shift(l, r, node);
    if(l == r) return tree[node];
    int mid = (l + r) / 2;
    if(idx <= mid) return query(l, mid, 2 * node, idx);
    return query(mid + 1, r, 2 * node + 1, idx);
}
int query(int idx){
    if(idx <= 0 || idx >= N) return -1;
    return query(1, N - 1, 1, idx);
}
pair <int, int> bounds(int idx){
    pair <int, int> ret;
    int cur = query(idx);
    {
        int l = 1, r = idx;
        while(l <= r){
            int mid = (l + r) / 2;
            if(query(mid) == cur) r = mid - 1;
            else l = mid + 1;
        }
        ret.first = l;
    }
    {
        int l = idx, r = N;
        while(l <= r){
            int mid = (l + r) / 2;
            if(query(mid) == cur) l = mid + 1;
            else r = mid - 1;
        }
        ret.second = r;
    }
    return ret;
}
void upd(int l, int r){
    if(r < l) return;
    update(1, N - 1, 1, l, r);
}
void update(int l, int r){
    int k = r - l + 1;
    auto b = bounds(l);
    b.second = min(b.second, r);
    upd(b.second + 1, r);
    k -= r - b.second;
    upd(b.first, b.first + k - 1);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    for(auto &i : a) cin >> i.first >> i.second;
    sort(a.begin(), a.end());
    for(auto &i : a){
        update(i.first - i.second + 1, i.first);
    }
    ll ans = 0;
    for(int i = 1 ; i < N ; i++){
        int cur = query(i);
        ans += 1LL * cur * (cur - 1) / 2;
    }
    cout << ans << endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 14 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 504 KB Output is correct
2 Correct 21 ms 2424 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1172 KB Output is correct
2 Correct 144 ms 988 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 1532 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 2424 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 3932 KB Output is correct
2 Correct 404 ms 4096 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 4216 KB Output is correct
2 Correct 267 ms 3208 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 4344 KB Output is correct
2 Correct 416 ms 2984 KB Output is correct