제출 #1244790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244790		Nika533	섬 항해 (CEOI13_adriatic)	C++20	0 / 100	428 ms	183056 KiB

adriatic

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=2505,M=25005;
int x[M],y[M];
int n,m,T,k,g[N][N],mxi[N][N],mxj[N][N],mni[N][N],mnj[N][N],pref[N][N],dp1n[N][N],dpn1[N][N];
int p(int i, int j) {
	if (i<0 || j<0) return 0;
	return pref[i][j];
}
int sum(int i1, int i2, int j1, int j2) {
	return p(i2,j2)-p(i1-1,j2)-p(i2,j1-1)+p(i1-1,j1-1);
}
void test_case() {
	cin>>m; n=2500;
	for (int i=1; i<=m; i++) {
		int a,b; cin>>a>>b;
		g[a][b]=1; x[i]=a; y[i]=b;
	}
	mni[0][0]=n+1; mnj[0][0]=n+1;
	for (int i=1; i<=n; i++) {
		mni[i][0]=n+1; mnj[i][0]=n+1;
		for (int j=1; j<=n; j++) {
			int I=n+1,J=n+1;
			if (g[i][j]) {
				I=i; J=j;
			}
			mni[i][j]=min(mni[i][j-1],I);
			mnj[i][j]=min(mnj[i][j-1],J);
			pref[i][j]=pref[i][j-1]+g[i][j];
		}
	}
	for (int j=1; j<=n; j++) {
		mni[0][j]=n+1; mnj[0][j]=n+1;
		for (int i=1; i<=n; i++) {
			mni[i][j]=min(mni[i-1][j],mni[i][j]);
			mnj[i][j]=min(mnj[i-1][j],mnj[i][j]);
			pref[i][j]=pref[i-1][j]+pref[i][j];
		}
	}
	mxi[n+1][n+1]=0; mnj[n+1][n+1]=0;
	for (int i=n; i>=1; i--) {
		mxi[i][n+1]=0; mxj[i][n+1]=0;
		for (int j=n; j>=1; j--) {
			int I=0,J=0;
			if (g[i][j]) {
				I=i; J=j;
			}
			mxi[i][j]=max(mxi[i][j+1],I);
			mxj[i][j]=max(mxj[i][j+1],J);
		}
	}
	for (int j=n; j>=1; j--) {
		mxi[n+1][j]=0; mxj[n+1][j]=0;
		for (int i=n; i>=1; i--) {
			mxi[i][j]=max(mxi[i+1][j],mxi[i][j]);
			mxj[i][j]=max(mxj[i+1][j],mxj[i][j]);
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=n; j>=1; j--) {
			int ii=mni[i-1][j-1],jj=mxj[i+1][j+1];
			ii=min(ii,i); jj=max(jj,j);
			if (i==ii && j==jj) continue;
			int num=sum(1,i,j,n)-g[i][j];
			dp1n[i][j]=dp1n[ii][jj]+num;
//			cout<<i<<" "<<j<<" "<<ii<<" "<<jj<<" "<<num<<" "<<dp1n[i][j]<<endl;
		}
	}
	for (int i=n; i>=1; i--) {
		for (int j=1; j<=n; j++) {
			int ii=mxi[i+1][j+1],jj=mnj[i-1][j-1];
			ii=max(ii,i); jj=min(jj,j);
			if (i==ii && j==jj) continue;
			int num=sum(i,n,1,j)-g[i][j];
			dpn1[i][j]=dpn1[ii][jj]+num;
//			cout<<"S "<<i<<" "<<j<<" "<<ii<<" "<<jj<<" "<<num<<" "<<dpn1[i][j]<<endl;
		}
	}
	for (int i=1; i<=m; i++) {
//		cout<<sum(1,x[i]-1,1,y[i]-1)+sum(x[i]+1,n,y[i]+1,n)+dp1n[x[i]][y[i]]+dpn1[x[i]][y[i]]<<endl;
		cout<<m-1+dp1n[x[i]][y[i]]+dpn1[x[i]][y[i]]<<endl;
	}
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1;
	while (T--) test_case();
}

컴파일 시 표준 에러 (stderr) 메시지

adriatic.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
adriatic.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main () {
      | ^~~~

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