Submission #1068467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068467		beaconmc	Sails (IOI07_sails)	C++14	60 / 100	1071 ms	9980 KiB

sails

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
const ll maxn = 200005;

ll tree[maxn*4];
ll lazy[maxn*4];

ll calc(ll k, ll x, ll y){
    return tree[k] + lazy[k] * (y-x+1);
}

void push(ll k, ll x, ll y){
    lazy[k*2] += lazy[k];
    lazy[k*2+1] += lazy[k];
    tree[k] += lazy[k] * (y-x+1);
    lazy[k] = 0;
}

void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y = maxn-1){
    if (y<a || x>b) return;
    if (a<=x && y<=b){
        lazy[k] += val;
        return;
    }
    push(k,x,y);
    ll mid  = (x+y)/2;
    update(a, b, val, k*2, x, mid);
    update(a, b, val, k*2+1, mid+1, y);

    tree[k] = calc(k*2, x, mid) + calc(k*2+1, mid+1, y);
}

ll query(ll a, ll b, ll k=1, ll x=0, ll y=maxn-1){
    if (y<a || x>b) return 0;
    if (a<=x && y<=b){
        return calc(k,x,y);
    }
    push(k,x,y);
    ll mid  = (x+y)/2;
    return query(a,b,k*2,x,mid) + query(a,b,k*2+1,mid+1,y);
}

int main(){
    ll n;
    cin >> n;
    vector<vector<ll>> stuff;
    FOR(i,0,n){
        ll h,k;
        cin >> h >> k;
        stuff.push_back({h,k});
    }

    sort(stuff.begin(), stuff.end());

    for (auto&i : stuff){

        ll num = i[1];
        num--;
        ll pos = n-i[0];


        ll val = query(pos+num, pos+num);

        ll lo = pos, hi = n-1;
        while (lo < hi){


            ll mid = (lo+hi+1)/2;


            ll temp = query(mid, mid);

            if (temp <= val) lo = mid;
            else hi = mid-1;
        }
        ll lasts = lo;

        lo = pos, hi = n;

        while (lo < hi){
            ll mid = (lo+hi)/2;

            ll temp = query(mid, mid);
            if (temp >= val) hi = mid;
            else lo = mid+1;
        }
        ll firsts = lo;


        update(pos, firsts-1, 1);


        ll overlap = pos+num - firsts;
        update(lasts-overlap, lasts, 1);


    }
    ll ans = 0;
    FOR(i,0,n){
        ll temp = query(i,i);

        ans += temp * (temp-1)/2;

    }
    cout << ans << endl;


}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 10 / 10