Submission #855486

#	Time	Username	Problem	Language	Result	Execution time	Memory
855486		AndiR	Sails (IOI07_sails)	C++14	100 / 100	74 ms	3820 KiB

sails

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

ll n, aib[Nmax];

void aib_add(ll l, ll r, ll val){
    while (l<Nmax){
        aib[l]+=val;
        l+=l&-l;
    }
    r++;
    while (r<Nmax){
        aib[r]-=val;
        r+=r&-r;
    }
}
ll aib_val(ll pos){
    ll s=0;
    while (pos>0){
        s+=aib[pos];
        pos-=pos&-pos;
    }
    return s;
}
ll aib_bs2(ll val, ll h){
    ll l=1, r=h, mij, v, sol=0;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v>=val){
            sol=mij;
            l=mij+1;
        }
        else r=mij-1;
    }
    return sol;
}
ll aib_bs1(ll val, ll h){
    ll l=1, r=h, mij, v, sol=0;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v<=val){
            sol=mij;
            r=mij-1;
        }
        else l=mij+1;
    }
    return sol;
}

struct mat{
    ll h, k;
}v[Nmax];

bool cmp(mat a, mat b){
    return a.h<b.h;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for (ll i=0; i<n; i++)
        cin>>v[i].h>>v[i].k;
    sort(v, v+n, cmp);
    for (ll i=0; i<n; i++){
        ll val=aib_val(v[i].h-v[i].k+1);
        ll l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
        ll st=v[i].k-(v[i].h-r+1);

        aib_add(r, v[i].h, 1);
        aib_add(l, l+st-1, 1);
    }
    ll sol=0;
    for (ll i=1; i<Nmax; i++){
        sol+=aib_val(i)*(aib_val(i)-1)/2;
    }
    cout<<sol;
    return 0;
}

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