Submission #914419

#	Time	Username	Problem	Language	Result	Execution time	Memory
914419		Keys	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	37 ms	8128 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
using vi = vector<int>;
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl '\n'
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
template <class T> istream &operator>>(istream& in, vector<T> &v) {for (auto& i : v) in >> i; return in;}

#ifdef LOCAL
#include "../../lib/debug.h"
#else
#define dbg(...)
#endif

const int N = 2e5 + 5;
int g[N][3];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  int ans = 0, top = 0, bot = 0;
  FOR(i, 0, 2 * n) {
    int x, y; cin >> x >> y;
    if (x < 1) ans += 1 - x, x = 1;
    if (x > n) ans += x - n, x = n; 

    if (y < 1) ans += 1 - y, y = 1;
    if (y > 2) ans += y - 2, y = 2; 

    g[x][y]++;
  }
  FOR(i, 1, n + 1) {
    top += g[i][2] - 1, bot += g[i][1] - 1;
    if ((top > 0) != (bot > 0)) {
      int x = min(abs(top), abs(bot));
      ans += x;
      if (top > 0) top -= x, bot += x;
      else top += x, bot -= x;
    }
    ans += abs(top) + abs(bot);
  }
  cout << ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63