Submission #837584

#	Time	Username	Problem	Language	Result	Execution time	Memory
837584		Andrey	Sails (IOI07_sails)	C++14	0 / 100	105 ms	22832 KiB

sails

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10