제출 #61872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61872		Benq	섬 항해 (CEOI13_adriatic)	C++11	100 / 100	435 ms	144600 KiB

adriatic

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2501;

template<class T, int SZ> struct sums {
    T sum[SZ][SZ];
    T maxX[SZ+1], maxY[SZ+1];
    T minX[SZ+1], minY[SZ+1];
    sums () { memset(sum,0,sizeof sum); }
    void init() {
        F0R(i,SZ+1) minX[i] = minY[i] = SZ;
        FOR(i,1,SZ) FOR(j,1,SZ) {
            if (sum[i][j]) {
                maxX[j] = max(maxX[j],i);
                maxY[i] = max(maxY[i],j);
                minX[j] = min(minX[j],i);
                minY[i] = min(minY[i],j);
            }
            sum[i][j] += sum[i][j-1]
            +sum[i-1][j]-sum[i-1][j-1];
        }
        FOR(i,1,SZ) {
            minY[i] = min(minY[i],minY[i-1]);
            minX[i] = min(minX[i],minX[i-1]);
        }
        FORd(i,1,SZ) {
            maxX[i] = max(maxX[i],maxX[i+1]);
            maxY[i] = max(maxY[i],maxY[i+1]);
        }
    }
    T get(int X1, int X2, int Y1, int Y2) {
        return sum[X2][Y2]-sum[X1-1][Y2]
        	-sum[X2][Y1-1]+sum[X1-1][Y1-1];
    }
};

sums<int,MX> S;

int N;
ll dp[2][MX][MX];
pi p[250001];

void gendp0() {
    FORd(i,1,MX) FOR(j,1,MX) { // currently have all points such that x < i or y > j
        dp[0][i][j] = S.get(i,MX-1,1,j);
        if (!dp[0][i][j]) continue;
        dp[0][i][j] += dp[0][max(i,S.maxX[j+1])][min(j,S.minY[i-1])];
    }
}

void gendp1() {
    FOR(i,1,MX) FORd(j,1,MX) {
        dp[1][i][j] = S.get(1,i,j,MX-1);
        if (!dp[1][i][j]) continue;
        dp[1][i][j] += dp[1][min(i,S.minX[j-1])][max(j,S.maxY[i+1])];
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    F0R(i,N) {
        cin >> p[i].f >> p[i].s;
        S.sum[p[i].f][p[i].s] ++;
    }
    S.init();
    gendp0();
    gendp1();
    
    F0R(i,N) cout << dp[0][p[i].f][p[i].s]+dp[1][p[i].f][p[i].s]+N-3 << "\n";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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