Submission #1283592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283592		behrad	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	33 ms	3436 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, x[maxn], y[maxn], cnt[maxn][3];

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n;
  ll ans = 0;
  for (int i = 1 ; i <= 2 * n ; i ++) {
    cin >> x[i] >> y[i];
    int nx = x[i], ny = y[i];
    if (nx < 1) nx = 1;
    if (nx > n) nx = n;
    if (ny < 1) ny = 1;
    if (ny > 2) ny = 2;

    ++ cnt[nx][ny];
    ans += abs(x[i] - nx) + abs(y[i] - ny);
  }

  for (int i = 1 ; i <= n ; i ++) -- cnt[i][1], -- cnt[i][2];

  for (int i = 1 ; i <= n ; i ++) {
    cnt[i][1] += cnt[i - 1][1];
    cnt[i][2] += cnt[i - 1][2];

    if(cnt[i][1]>0 && cnt[i][2]<0){
      int t = min(cnt[i][1], -cnt[i][2]);
      cnt[i][1] -= t;
      cnt[i][2] += t;
      ans += t;
    } else if (cnt[i][1] < 0 && cnt[i][2] > 0) {
      int t = min(-cnt[i][1], cnt[i][2]);
      cnt[i][1] += t;
      cnt[i][2] -= t;
      ans += t;
    }
    ans += abs(cnt[i][1]) + abs(cnt[i][2]);
  }
  cout << ans << nl;

}

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