Submission #291138

#	Time	Username	Problem	Language	Result	Execution time	Memory
291138		AlexPop28	Adriatic (CEOI13_adriatic)	C++11	100 / 100	449 ms	129528 KiB

adriatic

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20