oj.uz

Submission #630320

# Submission time Handle Problem Language Result Execution time Memory
630320 2022-08-16T07:42:46 Z andrei_boaca Adriatic (CEOI13_adriatic) C++14
100 / 100
 689 ms 104816 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 97980 KB Output is correct
2 Correct 369 ms 98088 KB Output is correct
3 Correct 401 ms 98056 KB Output is correct
4 Correct 61 ms 59952 KB Output is correct
5 Correct 430 ms 97864 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 98476 KB Output is correct
2 Correct 343 ms 98380 KB Output is correct
3 Correct 458 ms 98468 KB Output is correct
4 Correct 67 ms 61360 KB Output is correct
5 Correct 411 ms 96936 KB Output is correct
6 Correct 530 ms 98440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 98460 KB Output is correct
2 Correct 338 ms 98520 KB Output is correct
3 Correct 520 ms 98504 KB Output is correct
4 Correct 91 ms 65380 KB Output is correct
5 Correct 440 ms 98360 KB Output is correct
6 Correct 561 ms 98480 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 98972 KB Output is correct
2 Correct 343 ms 98940 KB Output is correct
3 Correct 564 ms 98932 KB Output is correct
4 Correct 124 ms 69684 KB Output is correct
5 Correct 411 ms 98728 KB Output is correct
6 Correct 595 ms 98988 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 104764 KB Output is correct
2 Correct 471 ms 104316 KB Output is correct
3 Correct 689 ms 104308 KB Output is correct
4 Correct 248 ms 84500 KB Output is correct
5 Correct 506 ms 103932 KB Output is correct
6 Correct 603 ms 104508 KB Output is correct
7 Correct 585 ms 104816 KB Output is correct