oj.uz

Submission #197546

# Submission time Handle Problem Language Result Execution time Memory
197546 2020-01-21T16:01:21 Z SamAnd Sails (IOI07_sails) C++17
100 / 100
 879 ms 6468 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4380 KB Output is correct
2 Correct 23 ms 4472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4600 KB Output is correct
2 Correct 22 ms 4472 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4472 KB Output is correct
2 Correct 21 ms 4472 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4468 KB Output is correct
2 Correct 25 ms 4472 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4444 KB Output is correct
2 Correct 30 ms 4484 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4648 KB Output is correct
2 Correct 187 ms 4984 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 4956 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 5524 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 6024 KB Output is correct
2 Correct 611 ms 6008 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 6468 KB Output is correct
2 Correct 367 ms 5880 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 6460 KB Output is correct
2 Correct 569 ms 6264 KB Output is correct