oj.uz

Submission #837584

# Submission time Handle Problem Language Result Execution time Memory
837584 2023-08-25T12:29:55 Z Andrey Sails (IOI07_sails) C++14
0 / 100
 105 ms 22832 KB 
#include<bits/stdc++.h>
using namespace std;

vector<long long> seg(1000001);
vector<long long> sb(800001);
vector<long long> big(800001);
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] = min(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,1000000);
    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);
        if(p+1 < a) {
            upd(0,200000,p+1,a,0,1);
        }
        long long p1 = banana(c+1,0,200000,0,0);
        if(p1+1 <= p1+b-(a-p)) {
            upd(0,200000,p1+1,p1+b-(a-p),0,1);
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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