oj.uz

Submission #291138

# Submission time Handle Problem Language Result Execution time Memory
291138 2020-09-04T18:27:57 Z AlexPop28 Adriatic (CEOI13_adriatic) C++11
100 / 100
 449 ms 129528 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int N = 2500;

template<class T> void Max(T &a, const T &b) { a = max(a, b); }
template<class T> void Min(T &a, const T &b) { a = min(a, b); }

void MakePrefix(vector<vector<int>> &a) {
  int n = a.size(), m = a[0].size();
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (i - 1 >= 0) a[i][j] += a[i - 1][j];
      if (j - 1 >= 0) a[i][j] += a[i][j - 1];
      if (i - 1 >= 0 && j - 1 >= 0) a[i][j] -= a[i - 1][j - 1];
    }
  }
}

vector<vector<int>> Solve(const vector<vector<int>> &pos) {
  int n = pos.size(), m = pos[0].size();
  vector<int> up(m, n), rgt(n, -1);
  for (int j = 0; j < m; ++j) {
    if (j != 0) up[j] = up[j - 1];
    for (int i = 0; i < up[j]; ++i) {
      if (pos[i][j]) {
        up[j] = i;
        break;
      }
    }
  }

  for (int i = n - 1; i >= 0; --i) { 
    if (i != n - 1) rgt[i] = rgt[i + 1];
    for (int j = m - 1; j > rgt[i]; --j) {
      if (pos[i][j]) {
        rgt[i] = j;
        break;
      }
    }
  }

  auto sum = pos;
  MakePrefix(sum);  

  auto Count = [&](int x, int y) {
    return sum[x][m - 1] - (y - 1 >= 0 ? sum[x][y - 1] : 0);
  };

  vector<vector<int>> dp(n, vector<int>(m));
  for (int i = 0; i < n; ++i) {
    for (int j = m - 1; j >= 0; --j) {
      int x = min(j - 1 >= 0 ? up[j - 1] : n, i);
      int y = max(i + 1 < n ? rgt[i + 1] : -1, j);

      dp[i][j] = dp[x][y] + Count(i, j) - pos[i][j] + pos[x][y];
    }
  }
  
  return dp;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n; cin >> n;
  vector<pair<int, int>> v(n);
  vector<vector<int>> pos(N, vector<int>(N));
  for (int i = 0; i < n; ++i) {
    int x, y; cin >> x >> y; --x, --y;
    v[i] = {x, y};
    ++pos[v[i].first][v[i].second];
  }
  
  auto up_lft = Solve(pos);
  
  vector<vector<int>> sop(N, vector<int>(N));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      sop[i][j] = pos[N - i - 1][N - j - 1];
    }
  }
  
  auto down_rgt = Solve(sop);

  for (int i = 0; i < n; ++i) {
    int x, y; tie(x, y) = v[i];
    cout << up_lft[x][y] + down_rgt[N - x - 1][N - y - 1] + n - 1 << '\n';
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 123168 KB Output is correct
2 Correct 217 ms 123128 KB Output is correct
3 Correct 264 ms 123256 KB Output is correct
4 Correct 291 ms 123128 KB Output is correct
5 Correct 271 ms 123128 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 123164 KB Output is correct
2 Correct 215 ms 123128 KB Output is correct
3 Correct 274 ms 123368 KB Output is correct
4 Correct 289 ms 123256 KB Output is correct
5 Correct 266 ms 123256 KB Output is correct
6 Correct 290 ms 123256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 123384 KB Output is correct
2 Correct 220 ms 123256 KB Output is correct
3 Correct 286 ms 123312 KB Output is correct
4 Correct 290 ms 123384 KB Output is correct
5 Correct 264 ms 123384 KB Output is correct
6 Correct 372 ms 123256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 123896 KB Output is correct
2 Correct 230 ms 123896 KB Output is correct
3 Correct 311 ms 123896 KB Output is correct
4 Correct 305 ms 123768 KB Output is correct
5 Correct 274 ms 124024 KB Output is correct
6 Correct 387 ms 123768 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 129332 KB Output is correct
2 Correct 360 ms 129144 KB Output is correct
3 Correct 413 ms 129272 KB Output is correct
4 Correct 381 ms 128888 KB Output is correct
5 Correct 351 ms 129528 KB Output is correct
6 Correct 444 ms 129420 KB Output is correct
7 Correct 443 ms 129528 KB Output is correct