Submission #430214

#TimeUsernameProblemLanguageResultExecution timeMemory
430214juancarlovieriCoin Collecting (JOI19_ho_t4)C++17
37 / 100
202 ms3008 KiB
#include <bits/stdc++.h>
using namespace std;

#define kath ash

int cnt[100005][5];

int main() {
  int n;
  cin >> n;
  long long ans = 0;
  for (int i = 0; i < 2 * n; ++i) {
    int x, y;
    cin >> x >> y;
    int nx = max(1, min(n, x));
    int ny = max(1, min(2, y));
    ++cnt[nx][ny];
    ans += abs(x - nx) + abs(y - ny);
  }
  vector<int> filled(3);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= 2; ++j) {
      int fill = min(i - filled[j], cnt[i][j]);
      ans += 1ll * (i - filled[j] - 1) * fill - fill * (fill - 1) / 2;
      filled[j] += fill;
      cnt[i][j] -= fill;
    }
    for (int j = 1; j <= 2; ++j) {
      int fill = min(i - filled[j % 2 + 1], cnt[i][j]);
      ans += 1ll * (i - filled[j % 2 + 1] - 1) * fill - fill * (fill - 1) / 2 + fill;
      filled[j % 2 + 1] += fill;
      cnt[i][j] -= fill;
    }
    if (i + 1 <= n) {
      for (int j = 1; j <= 2; ++j) {
        ans += cnt[i][j];
        cnt[i + 1][j] += cnt[i][j];
      }
    }
  }
  cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...