제출 #1317606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317606		Tymond	Adriatic (CEOI13_adriatic)	C++20	100 / 100	324 ms	225672 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l, int p){return uniform_int_distribution<int>(l, p)(rng);}
inline ll rand(ll l, ll p){return uniform_int_distribution<ll>(l, p)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

const int MAXK = 2507;
const int MAXN = 3e5 + 7;
pii A[MAXN];
int pref[MAXK][MAXK];
int rightmost[MAXK];
int leftmost[MAXK];
int highest[MAXK];
int lowest[MAXK];
pll dp1[MAXK][MAXK];
pll dp2[MAXK][MAXK];
int n;

int count(int c, int d, int a, int b){
	if(d < b || c < a){
		return 0;
	}
	//cerr << c << ' ' << d << ' ' << a << ' ' << b << ' ' << pref[c][d] - pref[c - 1][d] - pref[c][d - 1] + pref[c - 1][d - 1] << '\n';
	//cerr << pref[c][d] << ' ' << pref[c - 1][d] << ' ' << pref[c][d - 1] << ' ' << pref[c - 1][d- 1]
	return pref[c][d] - pref[a - 1][d] - pref[c][b - 1] + pref[a - 1][b - 1];
}

void preprocessing(){
	for(int i = MAXK - 2; i >= 1; i--){
		rightmost[i] = rightmost[i + 1];
		for(int j = 1; j < MAXK; j++){
			if(pref[i][j]){
				rightmost[i] = max(rightmost[i], j);
			}
		}
	}

	leftmost[0] = MAXK;
	for(int i = 1; i < MAXK; i++){
		leftmost[i] = leftmost[i - 1];
		for(int j = 1; j < MAXK; j++){
			if(pref[i][j]){
				leftmost[i] = min(leftmost[i], j);
			}
		}
	}

	for(int j = MAXK - 2; j >= 1; j--){
		highest[j] = highest[j + 1];
		for(int i = 1; i < MAXK; i++){
			if(pref[i][j]){
				highest[j] = max(highest[j], i);
			}
		}
	}

	lowest[0] = MAXK;
	for(int j = 1; j < MAXK; j++){
		lowest[j] = lowest[j - 1];
		for(int i = 1; i < MAXK; i++){
			if(pref[i][j]){
				lowest[j] = min(lowest[j], i);
			}
		}
	}

	for(int i = 1; i < MAXK; i++){
		for(int j = 1; j < MAXK; j++){
			pref[i][j] = pref[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
		}
	}
}

void countDp(){
	//najpierw dp1
	for(int i = 1; i < MAXK - 1; i++){
		for(int j = MAXK - 1; j >= 1; j--){
			int nx = lowest[j - 1];
			int ny = rightmost[i + 1];
			nx = min(nx, i);
			ny = max(ny, j);

			dp1[i][j] = dp1[nx][ny];
			dp1[i][j].fi += dp1[i][j].se;
			int dod = count(i, MAXK - 1, nx + 1, j) + count(i, ny - 1, 1, j) - count(i, ny - 1, nx + 1, j);
			dp1[i][j].fi += dod;
			dp1[i][j].se += dod;
		}
	}

	for(int i = MAXK - 1; i >= 1; i--){
		for(int j = 1; j + 1 < MAXK; j++){
			int nx = highest[j + 1];
			int ny = leftmost[i - 1];
			if(ny == MAXK && nx == 0){
				continue;
			}
			ny = min(ny, j);
			nx = max(nx, i);

			dp2[i][j] = dp2[nx][ny];
			dp2[i][j].fi += dp2[i][j].se;
			int dod = count(MAXK - 1, j, i, ny + 1) + count(nx - 1, j, i, 1) - count(nx - 1, j, i, ny + 1);
			dp2[i][j].fi += dod;
			dp2[i][j].se += dod;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> A[i].fi >> A[i].se;
		pref[A[i].fi][A[i].se]++;
	}

	preprocessing();
	countDp();
	for(int i = 1; i <= n; i++){
		ll ans = (ll)count(MAXK - 1, MAXK - 1, A[i].fi + 1, A[i].se + 1) + count(A[i].fi - 1, A[i].se - 1, 1, 1);
		//cerr << "===== " << i << '\n';
		//cerr << A[i].fi << ' ' << A[i].se << '\n';
		//cerr << count(MAXK - 1, MAXK - 1, A[i].fi + 1, A[i].se + 1) << ' ' << count(A[i].fi - 1, A[i].se - 1, 1, 1) << '\n';
		
		
		if(count(A[i].fi, MAXK - 1, 1, A[i].se) > 1){
			//debug(dp1[A[i].fi][A[i].se]);
			ans += (dp1[A[i].fi][A[i].se].fi + dp1[A[i].fi][A[i].se].se - 2);
		}
		
		if(count(MAXK - 1, A[i].se, A[i].fi, 1) > 1){
			//debug(dp2[A[i].fi][A[i].se]);
			ans += (dp2[A[i].fi][A[i].se].fi + dp2[A[i].fi][A[i].se].se - 2);
		}
		
		cout << ans << '\n';
	}

	return 0;
}

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