Submission #573399

#	Time	Username	Problem	Language	Result	Execution time	Memory
573399		DJ035	Adriatic (CEOI13_adriatic)	C++17	100 / 100	218 ms	158700 KiB

adriatic

#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]++;
    }
    memset(cn, 0x3f, sizeof(cn));
    memset(dn, 0x3f, sizeof(dn));
    //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(dx[b[i].x], b[i].y);
        dn[b[i].y] = min(dn[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; i--){
        for(ll j=1; j<=MX; j++){
            r=max(cx[j+1], i), c=min(cn[i-1], j);
            dp[i][j] = dp[r][c]+sum(i,MX,1LL,j);
        }
    }
    //cout << 'd';
    for(ll i=1; i<=MX; i++){
        for(ll j=MX; j; j--){
            r=min(dn[j-1], i), c=max(dx[i+1], j);
            dp2[i][j] = dp2[r][c]+sum(1LL,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';
    }
}

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