Submission #630320

#	Time	Username	Problem	Language	Result	Execution time	Memory
630320		andrei_boaca	Adriatic (CEOI13_adriatic)	C++14	100 / 100	689 ms	104816 KiB

adriatic

#include <bits/stdc++.h>
#define NMAX 2500
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
struct point
{
    int x,y;
} v[250005];
int sol[250005];
int s[2505][2505],dp1[2505][2505],dp2[2505][2505],cnt[2505][2505];
int getsum(int i1,int j1,int i2,int j2)
{
    if(i1<1||j1<1||i2>NMAX||j2>NMAX)
        return 0;
    return s[i2][j2]-s[i1-1][j2]-s[i2][j1-1]+s[i1-1][j1-1];
}
bool iseq(point a, point b)
{
    return a.x==b.x&&a.y==b.y;
}
int biglin[2505],bigcol[2505],smalllin[2505],smallcol[2505];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=NMAX;i++)
        biglin[i]=0,bigcol[i]=0,smalllin[i]=1e9,smallcol[i]=1e9;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        biglin[v[i].x]=max(biglin[v[i].x],v[i].y);
        bigcol[v[i].y]=max(bigcol[v[i].y],v[i].x);
        smalllin[v[i].x]=min(smalllin[v[i].x],v[i].y);
        smallcol[v[i].y]=min(smallcol[v[i].y],v[i].x);
        s[v[i].x][v[i].y]=1;
    }
    for(int a=2;a<=NMAX;a++)
    {
        smalllin[a]=min(smalllin[a],smalllin[a-1]);
        smallcol[a]=min(smallcol[a],smallcol[a-1]);
    }
    for(int a=NMAX-1;a>=1;a--)
    {
        biglin[a]=max(biglin[a],biglin[a+1]);
        bigcol[a]=max(bigcol[a],bigcol[a+1]);
    }
    for(int i=1;i<=NMAX;i++)
        for(int j=1;j<=NMAX;j++)
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    for(int i=1;i<=NMAX;i++)
        for(int j=NMAX;j>=1;j--)
        {
            cnt[i][j]=getsum(1,j,i,NMAX);
            if(cnt[i][j]==0)
                continue;
            int minR=i,maxC=j;
            /*for(int a=1;a<=i;a++)
                if(smalllin[a]<j)
                {
                    minR=a;
                    break;
                }*/
            int st=1;
            int dr=i;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(smalllin[mij]<j)
                {
                    minR=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            /*for(int a=NMAX;a>=j;a--)
                if(bigcol[a]>i)
                {
                    maxC=a;
                    break;
                }*/
            st=j;
            dr=NMAX;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(bigcol[mij]>i)
                {
                    maxC=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            dp1[i][j]=cnt[i][j]+dp1[minR][maxC];
        }
    for(int i=NMAX;i>=1;i--)
        for(int j=1;j<=NMAX;j++)
        {
            cnt[i][j]=getsum(i,1,NMAX,j);
            if(cnt[i][j]==0)
                continue;
            int maxR=i,minC=j;
            /*for(int a=NMAX;a>=i;a--)
                if(biglin[a]>j)
                {
                    maxR=a;
                    break;
                }*/
            int st=i;
            int dr=NMAX;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(biglin[mij]>j)
                {
                    maxR=mij;
                    st=mij+1;
                }
                else
                    dr=mij-1;
            }
            /*for(int a=1;a<=j;a++)
                if(smallcol[a]<i)
                {
                    minC=a;
                    break;
                }*/
            st=1;
            dr=j;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(smallcol[mij]<i)
                {
                    minC=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            dp2[i][j]=cnt[i][j]+dp2[maxR][minC];
        }
    for(int i=1;i<=n;i++)
    {
        int lin=v[i].x,col=v[i].y;
        int suma=n-1;
        suma+=dp1[lin][col]+dp2[lin][col]-2;
        cout<<suma<<'\n';
    }
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20