Submission #143917

#TimeUsernameProblemLanguageResultExecution timeMemory
143917MilkiAdriatic (CEOI13_adriatic)C++14
50 / 100
334 ms182736 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = a; i < b; ++i) #define REP(i, n) FOR(i, 0, n) #define _ << " " << #define sz(x) ((int) x.size()) #define pb(x) push_back(x) #define TRACE(x) cerr << #x << " = " << x << endl typedef long long ll; typedef pair<int, int> point; const int MAXN = 2505, inf = 1e9, MAX = 2500; int n, total[MAXN][MAXN]; bool imam[MAXN][MAXN]; struct Sum{ int X[MAXN][MAXN], Y[MAXN][MAXN]; Sum(){} void init_prefix(){ REP(i, MAXN) REP(j, MAXN) X[i][j] = Y[i][j] = inf; } void init_suffix(){ REP(i, MAXN) REP(j, MAXN) X[i][j] = Y[i][j] = 0; } void update_prefix(int x, int y){ X[x][y] = min(X[x - 1][y], X[x][y - 1]); Y[x][y] = min(Y[x - 1][y], Y[x][y - 1]); if(imam[x][y]){ X[x][y] = min(X[x][y], x); Y[x][y] = min(Y[x][y], y); } } void update_suffix(int x, int y){ X[x][y] = max(X[x + 1][y], X[x][y + 1]); Y[x][y] = max(Y[x + 1][y], Y[x][y + 1]); if(imam[x][y]){ X[x][y] = max(X[x][y], x); Y[x][y] = max(Y[x][y], y); } } } prefix, suffix; int dp_lt[MAXN][MAXN], dp_rt[MAXN][MAXN]; point in[MAXN]; int get(int x1, int y1, int x2, int y2){ return total[x2][y2] - total[x1 - 1][y2] - total[x2][y1 - 1] + total[x1 - 1][y1 - 1]; } int rek_lt(int x, int y){ //TRACE("OK"); TRACE(x); TRACE(y); //TRACE(get(x, 1, MAX, y)); //TRACE(dp_lt[x][y]); if(dp_lt[x][y] != -1) { return dp_lt[x][y]; } if(get(x, 1, MAX, y) == 1) return dp_lt[x][y] = 1; int mx_x = suffix.X[x][y + 1], mn_y = prefix.Y[x - 1][y]; if(mx_x == x && mn_y == y) return dp_lt[x][y] = 0; return dp_lt[x][y] = get(x, 1, MAX, y) + rek_lt( max(mx_x, x), min(mn_y, y) ); } int rek_rt(int x, int y){ //TRACE(x); TRACE(y); TRACE("KOK"); TRACE(get(1, y, x, MAX)); if(dp_rt[x][y] != -1) return dp_rt[x][y]; if(get(1, y, x, MAX) == 1) return dp_rt[x][y] = 1; //TRACE(x); TRACE(y); int mn_x = prefix.X[x][y - 1], mx_y = suffix.Y[x + 1][y]; if(mn_x == x && mx_y == y) return dp_rt[x][y] = 0; return dp_rt[x][y] = get(1, y, x, MAX) + rek_rt( min(mn_x, x), max(mx_y, y) ); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); memset(dp_lt, -1, sizeof(dp_lt)); memset(dp_rt, -1, sizeof(dp_rt)); prefix.init_prefix(); suffix.init_suffix(); cin >> n; REP(i, n){ int a, b; cin >> a >> b; imam[a][b] = 1; in[i] = point(a, b); } FOR(i, 1, MAX + 1) FOR(j, 1, MAX + 1){ prefix.update_prefix(i, j); total[i][j] = total[i][j - 1] + total[i - 1][j] - total[i - 1][j - 1] + imam[i][j]; } for(int i = MAX; i > 0; --i) for(int j = MAX; j > 0; --j) suffix.update_suffix(i, j); REP(i, n){ int x = in[i].first, y = in[i].second; cout << rek_lt(x, y) + rek_rt(x, y) + total[MAX][MAX] - 3 << "\n"; //break; } }
#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...