oj.uz

Submission #245200

# Submission time Handle Problem Language Result Execution time Memory
245200 2020-07-05T17:27:18 Z TadijaSebez Adriatic (CEOI13_adriatic) C++11
60 / 100
 2000 ms 147704 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 153 ms 123512 KB Output is correct
2 Correct 149 ms 123384 KB Output is correct
3 Correct 142 ms 123384 KB Output is correct
4 Correct 143 ms 123128 KB Output is correct
5 Correct 146 ms 123384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 127584 KB Output is correct
2 Correct 147 ms 128396 KB Output is correct
3 Correct 148 ms 127736 KB Output is correct
4 Correct 152 ms 123512 KB Output is correct
5 Correct 145 ms 123900 KB Output is correct
6 Correct 191 ms 125816 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 131576 KB Output is correct
2 Correct 157 ms 136896 KB Output is correct
3 Correct 168 ms 132088 KB Output is correct
4 Correct 153 ms 124664 KB Output is correct
5 Correct 146 ms 124436 KB Output is correct
6 Correct 804 ms 133240 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1337 ms 134488 KB Output is correct
2 Correct 179 ms 147704 KB Output is correct
3 Correct 228 ms 134392 KB Output is correct
4 Correct 157 ms 126456 KB Output is correct
5 Correct 160 ms 125820 KB Output is correct
6 Execution timed out 2100 ms 134456 KB Time limit exceeded

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 138616 KB Time limit exceeded
2 Halted 0 ms 0 KB -