Submission #521585

#	Time	Username	Problem	Language	Result	Execution time	Memory
521585		andrei_boaca	Sails (IOI07_sails)	C++17	100 / 100	127 ms	3720 KiB

sails

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;
ll aib[100005];
ll lg;
struct date
{
    ll h,k;
} v[100005];
bool comp(date a, date b)
{
    return a.h<b.h;
}
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=lg;i+=lsb(i))
        aib[i]+=val;
}
ll query(int poz)
{
    ll rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].h>>v[i].k;
    sort(v+1,v+n+1,comp);
    lg=v[n].h;
    for(int i=1;i<=n;i++)
    {
        ll k=v[i].k;
        ll h=v[i].h;
        ll nr=query(h-k+1);
        ll first=h+1;
        ll st=1;
        ll dr=h;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(query(mij)<nr)
            {
                first=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        if(first<=h)
        {
            update(first,+1);
            update(h+1,-1);
        }
        ll lft=k-(h-first+1);
        st=1;
        dr=h;
        first=h;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(query(mij)<=nr)
            {
                first=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        update(first,+1);
        update(first+lft,-1);
    }
    ll ans=0;
    for(int i=1;i<=lg;i++)
    {
        ll val=query(i);
        ans+=val*(val-1)/2;
    }
    cout<<ans;
    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