oj.uz

Submission #837629

# Submission time Handle Problem Language Result Execution time Memory
837629 2023-08-25T13:18:30 Z Andrey Sails (IOI07_sails) C++14
100 / 100
 166 ms 26900 KB 
#include<bits/stdc++.h>
using namespace std;

vector<long long> seg(1000001);
vector<long long> sb(1000001);
vector<long long> big(1000001);
long long yo;

void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) {
    if(l == ql && r == qr) {
        seg[x]+=br;
        big[x]+=br;
        sb[x]+=br*(r-l+1);
        return;
    }
    long long m = (l+r)/2;
    if(qr <= m) {
        upd(l,m,ql,qr,x*2+1,br);
    }
    else if(ql > m) {
        upd(m+1,r,ql,qr,x*2+2,br);
    }
    else {
        upd(l,m,ql,m,x*2+1,br);
        upd(m+1,r,m+1,qr,x*2+2,br);
    }
    big[x] = max(big[x*2+1],big[x*2+2])+seg[x];
    sb[x] = sb[x*2+1]+sb[x*2+2]+seg[x]*(r-l+1);
}

long long calc(long long l, long long r, long long ql, long long qr, long long x, long long br) {
    if(l == ql && r == qr) {
        return sb[x]+br*(r-l+1);
    }
    long long m = (l+r)/2;
    if(qr <= m) {
        return calc(l,m,ql,qr,x*2+1,br+seg[x]);
    }
    else if(ql > m) {
        return calc(m+1,r,ql,qr,x*2+2,br+seg[x]);
    }
    else {
        return calc(l,m,ql,m,x*2+1,br+seg[x])+calc(m+1,r,m+1,qr,x*2+2,br+seg[x]);
    }
}

long long banana(long long a, long long l, long long r, long long x, long long br) {
    if(l == r) {
        return l;
    }
    long long m = (l+r)/2;
    br+=seg[x];
    if(br+big[x*2+2] < a || m+1 > yo) {
        return banana(a,l,m,x*2+1,br);
    }
    else {
        return banana(a,m+1,r,x*2+2,br);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,a,b,ans = 0;
    cin >> n;
    vector<pair<long long,long long>> haha(0);
    vector<long long> yay(0);
    for(long long i = 0; i < n; i++) {
        cin >> a >> b;
        haha.push_back({a,b});
    }
    sort(haha.begin(),haha.end());
    upd(0,200000,0,0,0,10000000);
    for(long long i = 0; i < n; i++) {
        a = haha[i].first;
        b = haha[i].second;
        yo = a;
        ans+=calc(0,200000,a-b+1,a,0,0);
        long long c = calc(0,200000,a-b+1,a-b+1,0,0);
        long long p = banana(c,0,200000,0,0);
        long long p1 = banana(c+1,0,200000,0,0);
        if(p+1 <= a) {
            upd(0,200000,p+1,a,0,1);
        }
        upd(0,200000,p1+1,p1+b-(a-p),0,1);
    }
    cout << ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23816 KB Output is correct
2 Correct 9 ms 23728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23720 KB Output is correct
2 Correct 8 ms 23764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23764 KB Output is correct
2 Correct 8 ms 23764 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 9 ms 23732 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23948 KB Output is correct
2 Correct 47 ms 24732 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 24408 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 24872 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 25936 KB Output is correct
2 Correct 104 ms 26860 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 25956 KB Output is correct
2 Correct 54 ms 26648 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 25976 KB Output is correct
2 Correct 92 ms 26900 KB Output is correct