oj.uz

Submission #143954

# Submission time Handle Problem Language Result Execution time Memory
143954 2019-08-15T13:35:31 Z Milki Adriatic (CEOI13_adriatic) C++14
100 / 100
 449 ms 184868 KB 
#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 * 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){
  if(dp_lt[x][y] != -1) { return dp_lt[x][y]; }
  if(get(x, 1, MAX, y) == 1) return dp_lt[x][y] = 1;
  if(get(x, 1, MAX, y) == 0) return dp_lt[x][y] = 0;

  int mx_x = suffix.X[x][y + 1], mn_y = prefix.Y[x - 1][y];
  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){
  if(dp_rt[x][y] != -1) return dp_rt[x][y];
  if(get(1, y, x, MAX) == 1) return dp_rt[x][y] = 1;
  if(get(1, y, x, MAX) == 0) return dp_rt[x][y] = 0;

  int mn_x = prefix.X[x][y - 1], mx_y = suffix.Y[x + 1][y];
  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";
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 172588 KB Output is correct
2 Correct 196 ms 172604 KB Output is correct
3 Correct 195 ms 172724 KB Output is correct
4 Correct 195 ms 172240 KB Output is correct
5 Correct 198 ms 172508 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 175852 KB Output is correct
2 Correct 197 ms 175992 KB Output is correct
3 Correct 195 ms 175988 KB Output is correct
4 Correct 196 ms 172536 KB Output is correct
5 Correct 197 ms 172852 KB Output is correct
6 Correct 198 ms 174908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 177960 KB Output is correct
2 Correct 204 ms 178264 KB Output is correct
3 Correct 208 ms 178208 KB Output is correct
4 Correct 197 ms 173084 KB Output is correct
5 Correct 219 ms 173432 KB Output is correct
6 Correct 199 ms 178516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 179040 KB Output is correct
2 Correct 216 ms 179020 KB Output is correct
3 Correct 230 ms 178936 KB Output is correct
4 Correct 208 ms 173944 KB Output is correct
5 Correct 207 ms 174232 KB Output is correct
6 Correct 211 ms 179036 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 184564 KB Output is correct
2 Correct 381 ms 184492 KB Output is correct
3 Correct 449 ms 184356 KB Output is correct
4 Correct 351 ms 180344 KB Output is correct
5 Correct 354 ms 180448 KB Output is correct
6 Correct 348 ms 184568 KB Output is correct
7 Correct 343 ms 184868 KB Output is correct