Submission #245200

#	Time	Username	Problem	Language	Result	Execution time	Memory
245200		TadijaSebez	Adriatic (CEOI13_adriatic)	C++11	60 / 100	2100 ms	147704 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
const int N=250050;
const int inf=1e9+7;
int x[N],y[N];
int dist[N];
const int M=2505;
int sum[M][M],cell[M][M];
int Get(int xl,int yl,int xr,int yr){
	if(xl>xr||yl>yr)return 0;
	return sum[xr][yr]-sum[xr][yl-1]-sum[xl-1][yr]+sum[xl-1][yl-1];
}
pii mn[M][M],mx[M][M];
void ckmn(int&x,int y){x=min(x,y);}
void ckmn(pii&x,pii y){ckmn(x.first,y.first);ckmn(x.second,y.second);}
void ckmx(int&x,int y){x=max(x,y);}
void ckmx(pii&x,pii y){ckmx(x.first,y.first);ckmx(x.second,y.second);}
int main(){
	int n;scanf("%i",&n);
	for(int i=1;i<=n;i++)scanf("%i %i",&x[i],&y[i]),sum[x[i]][y[i]]=cell[x[i]][y[i]]=1;

	/*mt19937 rng(time(0));
	int n=250000;
	for(int i=1;i<=n;i++){
		do{
			x[i]=rng()%2500+1;
			y[i]=rng()%2500+1;
		}while(sum[x[i]][y[i]]);
		sum[x[i]][y[i]]=1;
	}*/

	for(int i=0;i<M;++i)for(int j=0;j<M;++j)mn[i][j]={inf,inf};
	for(int i=1;i<=2500;++i)
		for(int j=1;j<=2500;++j){
			ckmn(mn[i][j],mn[i-1][j]);
			ckmn(mn[i][j],mn[i][j-1]);
			if(sum[i][j])ckmn(mn[i][j],(pii){i,j});
		}
	for(int i=2500;i>=1;--i)
		for(int j=2500;j>=1;--j){
			ckmx(mx[i][j],mx[i+1][j]);
			ckmx(mx[i][j],mx[i][j+1]);
			if(sum[i][j])ckmx(mx[i][j],(pii){i,j});
		}
	for(int i=1;i<=2500;++i)
		for(int j=1;j<=2500;++j)
			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];

	//set<array<int,4>> all;
	//int cnt=0;

	for(int ptr=1;ptr<=n;++ptr){
		int X1=x[ptr],Y1=y[ptr];
		int X2=X1,Y2=Y1;
		ll ans=0;
		int exp=1;
		//printf("%i %i\n",X1,Y1);
		//pii was1,was2;
		ans+=n-1;
		for(int dist=1;exp<n;++dist){
			//all.insert({X1,Y1,X2,Y2});
			//cnt++;

			int now=0;
			now=Get(1,1,X2-1,Y2-1)+Get(X1+1,Y1+1,2500,2500)-Get(X1+1,Y1+1,X2-1,Y2-1);
			if(dist==1)now++;
			//now-=exp;
			/*if(dist==1){
				now+=Get(1,1,X2-1,Y2-1);
				now+=Get(X1+1,Y1+1,2500,2500);
			}else{
				now+=Get(was2.first,1,X2-1,was1.second);
				now+=Get(1,was2.second,was1.first,Y2-1);
				if(dist==2)now--;
				now+=Get(X2,Y1+1,2500,was1.second);
				now+=Get(X1+1,Y2,was1.first,2500);
				if(dist==2)now--;
			}*/
			//was1={X1,Y1};
			//was2={X2,Y2};
			pii tmp1=mn[X2-1][Y2-1];
			ckmn(tmp1,{X1,Y1});
			pii tmp2=mx[X1+1][Y1+1];
			ckmx(tmp2,{X2,Y2});
			//tie(X1,Y1,X2,Y2)=(tuple<int,int,int,int>){mn[X2-1][Y2-1].first,mn[X2-1][Y2-1].second,mx[X1+1][Y1+1].first,mx[X1+1][Y1+1].second};
			tie(X1,Y1)=tmp1;
			tie(X2,Y2)=tmp2;
			//printf("%i %i %i %i -> %i\n",X1,Y1,X2,Y2,now);
			//ans+=(ll)now*dist;
			ans+=n-now;
			exp=now;
			//assert(now!=0);
			//if(now==0)break;
		}
		printf("%lld\n",ans);
	}
	//printf("%i %i\n",all.size(),cnt);
	/*for(int i=1;i<=n;i++){
		queue<int> q;
		for(int j=1;j<=n;j++)dist[j]=inf;
		dist[i]=0;
		q.push(i);
		int ans=0;
		while(q.size()){
			int u=q.front();
			q.pop();
			ans+=dist[u];
			for(int v=1;v<=n;v++)
				if((x[v]<x[u]&&y[v]<y[u])||(x[u]<x[v]&&y[u]<y[v]))
					if(dist[v]>dist[u]+1)
						dist[v]=dist[u]+1,
						q.push(v);
		}
		printf("%i\n",ans);
	}*/
	return 0;
}

Compilation message (stderr)

adriatic.cpp: In function 'int main()':
adriatic.cpp:21:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n;scanf("%i",&n);
        ~~~~~^~~~~~~~~
adriatic.cpp:22:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i %i",&x[i],&y[i]),sum[x[i]][y[i]]=cell[x[i]][y[i]]=1;
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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