oj.uz

Submission #466377

# Submission time Handle Problem Language Result Execution time Memory
466377 2021-08-19T05:11:34 Z jli12345 Sails (IOI07_sails) C++14
100 / 100
 280 ms 10344 KB 
#include <bits/stdc++.h>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

int N;

pair<int, int> arr[100100];

long long st[400100];
long long stmax[400100];
long long stmin[400100];
long long addtag[400100];

void pushdown(int node, int l, int mid, int r){
    st[node*2] += addtag[node]*(mid-l+1);
    st[node*2+1] += addtag[node]*(r-mid);
    stmin[node*2] += addtag[node];
    stmin[node*2+1] += addtag[node];
    stmax[node*2] += addtag[node];
    stmax[node*2+1] += addtag[node];
    addtag[node*2] += addtag[node];
    addtag[node*2+1] += addtag[node];
    addtag[node] = 0;
}

void U(int node, int l, int r, int tl, int tr, int val){
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node] += (long long)(r-l+1)*val;
        stmin[node] += val;
        stmax[node] += val;
        addtag[node] += val;
        return;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    U(node*2, l, mid, tl, tr, val);
    U(node*2+1, mid+1, r, tl, tr, val);
    st[node] = st[node*2]+st[node*2+1];
    stmin[node] = min(stmin[node*2], stmin[node*2+1]);
    stmax[node] = max(stmax[node*2], stmax[node*2+1]);
}

long long S(int node, int l, int r, int ind){
    if (l > ind || r < ind)
        return 0;
    if (l == r){
        return st[node];
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    return S(node*2, l, mid, ind)+S(node*2+1, mid+1, r, ind);
}

long long lb(int node, int l, int r, int val){
    if (l == r)
        return l;
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    if (stmin[node*2] <= val){
        return lb(node*2, l, mid, val);
    } else {
        return lb(node*2+1, mid+1, r, val);
    }
}

long long rb(int node, int l, int r, int val){
    if (l == r)
        return l;
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    if (stmax[node*2+1] >= val){
        return rb(node*2+1, mid+1, r, val);
    } else {
        return rb(node*2, l, mid, val);
    }
}

int main(){
    fastIO();
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr+1, arr+1+N);
    //for (int i = 1; i <= N; i++)
        //cout << arr[i].first << " " << arr[i].second << "\n";
    for (int i = 1; i <= N; i++){
        int val = S(1, 1, 100000, arr[i].first-arr[i].second+1);
        int l = lb(1, 1, 100000, val);
        int r = min((long long)arr[i].first, rb(1, 1, 100000, val));
        //cout << val << " " << l << " " << r << "\n";
        if (r < arr[i].first)
            U(1, 1, 100000, r+1, arr[i].first, 1);
        U(1, 1, 100000, l, l+arr[i].second-(arr[i].first-r)-1, 1);
    }
    long long ans = 0;
    for (int i = 1; i <= 100000; i++){
        long long cnt = S(1, 1, 100000, i);
        ans += (cnt)*(cnt-1)/2;
    }
    cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8524 KB Output is correct
2 Correct 34 ms 8428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8524 KB Output is correct
2 Correct 27 ms 8516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8520 KB Output is correct
2 Correct 26 ms 8520 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8532 KB Output is correct
2 Correct 27 ms 8484 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8560 KB Output is correct
2 Correct 30 ms 8648 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8516 KB Output is correct
2 Correct 82 ms 9036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8736 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8800 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 9056 KB Output is correct
2 Correct 186 ms 10108 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 9156 KB Output is correct
2 Correct 130 ms 9932 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 9260 KB Output is correct
2 Correct 201 ms 10344 KB Output is correct