oj.uz

Submission #837621

# Submission time Handle Problem Language Result Execution time Memory
837621 2023-08-25T13:09:03 Z Andrey Sails (IOI07_sails) C++14
10 / 100
 155 ms 26008 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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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