Submission #197546

#	Time	Username	Problem	Language	Result	Execution time	Memory
197546		SamAnd	Sails (IOI07_sails)	C++17	100 / 100	879 ms	6468 KiB

sails

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N=100005,M=100000;
struct ban
{
    int h,k;
};
bool operator<(const ban& a,const ban& b)
{
    if(a.h<b.h)
        return true;
    if(a.h>b.h)
        return false;
    return a.k<b.k;
}

int n;
ban a[N];

long long t[N*4];
long long laz[N*4];

void shi(int tl,int tr,int pos)
{
    int m=(tl+tr)/2;
    t[pos*2]+=(laz[pos]*(m-tl+1));
    t[pos*2+1]+=(laz[pos]*(tr-m));
    laz[pos*2]+=laz[pos];
    laz[pos*2+1]+=laz[pos];
    laz[pos]=0;
}

void ubd(int tl,int tr,int l,int r,int pos)
{
    if(r<l)
        return;
    if(tl==l && tr==r)
    {
        t[pos]+=(r-l+1);
        laz[pos]++;
        return;
    }
    shi(tl,tr,pos);
    int m=(tl+tr)/2;
    if(r<=m)
        ubd(tl,m,l,r,pos*2);
    else if(l>m)
        ubd(m+1,tr,l,r,pos*2+1);
    else
    {
        ubd(tl,m,l,m,pos*2);
        ubd(m+1,tr,m+1,r,pos*2+1);
    }
    t[pos]=t[pos*2]+t[pos*2+1];
}

long long qry(int tl,int tr,int l,int r,int pos)
{
    if(tl==l && tr==r)
        return t[pos];
    shi(tl,tr,pos);
    int m=(tl+tr)/2;
    if(r<=m)
        return qry(tl,m,l,r,pos*2);
    if(l>m)
        return qry(m+1,tr,l,r,pos*2+1);
    return qry(tl,m,l,m,pos*2)+qry(m+1,tr,m+1,r,pos*2+1);
};

int bynr(int h,int k)
{
    long long t=qry(1,M,h-k+1,h-k+1,1);
    int l=h-k+1,r=h;
    while((r-l)>3)
    {
        int m=(l+r)/2;
        if(qry(1,M,m,m,1)==t)
            l=m;
        else
            r=m;
    }
    for(int m=r;m>=l;--m)
        if(qry(1,M,m,m,1)==t)
            return m;
}

int bynl(int h,int k)
{
    long long t=qry(1,M,h-k+1,h-k+1,1);
    int l=1,r=h-k+1;
    while((r-l)>3)
    {
        int m=(l+r)/2;
        if(qry(1,M,m,m,1)==t)
            r=m;
        else
            l=m;
    }
    for(int m=l;m<=r;++m)
        if(qry(1,M,m,m,1)==t)
            return m;
}

int main()
{
    //freopen("input.txt","r",stdin);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i].h>>a[i].k;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
    {
        int h=a[i].h,k=a[i].k;
        int r=bynr(h,k);
        int l=bynl(h,k);
        ubd(1,M,r+1,h,1);
        int d=r-(h-k+1)+1;
        ubd(1,M,l,l+d-1,1);
        //cout<<x-a[i].k+1<<' '<<x<<endl;
    }
    long long ans=0;
    for(int i=1;i<=100000;++i)
    {
        long long p=qry(1,M,i,i,1);
        if(p)
            ans+=((p*(p-1))/2);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int bynr(int, int)':
sails.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
sails.cpp: In function 'int bynl(int, int)':
sails.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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