Submission #573397

#TimeUsernameProblemLanguageResultExecution timeMemory
573397DJ035Adriatic (CEOI13_adriatic)C++17
0 / 100
184 ms156344 KiB
#include <bits/stdc++.h> #define MEM 2555 #define sanic ios_base::sync_with_stdio(0) #define x first #define y second #define sz size() #define pb push_back #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair<ll, ll> pi; const ll INF = 1e18+7; const ll MOD = 1e9+7; ll MX = 2500; ll gcd(ll a, ll b){ if(a%b) return gcd(b, a%b); return b; } string s; ll n; ll a[MEM][MEM]; pi b[252525]; ll cn[MEM], cx[MEM], dn[MEM], dx[MEM]; ll dp[MEM][MEM], dp2[MEM][MEM]; ll sum(ll sx, ll ex, ll sy, ll ey){ return a[ex][ey]-a[sx-1][ey]-a[ex][sy-1]+a[sx-1][sy-1]; } signed main(){ sanic; cin.tie(0); cout.tie(0); cin >> n; for(int i=1; i<=n; i++){ cin >> b[i].x >> b[i].y; a[b[i].x][b[i].y]++; } for(int i=0; i<MEM; i++) cn[i] = dn[i] = INF; //cout << 'd'; for(int i=1; i<=n; i++){ cn[b[i].x] = min(cn[b[i].x], b[i].y); cx[b[i].y] = max(cx[b[i].y], b[i].x); dx[b[i].x] = max(cn[b[i].x], b[i].y); dn[b[i].y] = min(cx[b[i].y], b[i].x); } //cout << 'd'; for(int i=1; i<=MX; i++){ cn[i] = min(cn[i], cn[i-1]); dn[i] = min(dn[i], dn[i-1]); cx[MX-i+1] = max(cx[MX-i+1], cx[MX-i+2]); dx[MX-i+1] = max(dx[MX-i+1], dx[MX-i+2]); } //cout << 'd'; for(int i=1; i<=MX; i++){ for(int j=1; j<=MX; j++){ a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1]; } } //cout << 'd'; ll r,c; for(ll i=MX; i>=1; i--){ for(ll j=1; j<=MX; j++){ c=min(cn[i-1], j), r=max(cx[j+1], i); dp[i][j] = dp[r][c]+sum(i,MX,1,j); } } //cout << 'd'; for(ll i=1; i<=MX; i++){ for(ll j=MX; j>=1; j--){ r=min(dn[j-1], i), c=max(dx[i+1], j); dp2[i][j] = dp2[r][c]+sum(1,i,j,MX); } } //cout << 'd'; for(int i=1; i<=n; i++){ cout << dp[b[i].x][b[i].y]+dp2[b[i].x][b[i].y]+n-3 << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...