Submission #416092

#TimeUsernameProblemLanguageResultExecution timeMemory
416092meatrowCoin Collecting (JOI19_ho_t4)C++17
100 / 100
96 ms5680 KiB
// #pragma GCC target ("avx2") // #pragma GCC optimization ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MOD = 1e9 + 7; ll binpow(ll a, ll p, int mod = MOD) { ll res = 1; while (p) { if (p & 1) { (res *= a) %= mod; } p >>= 1; (a *= a) %= mod; } return res; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll squeeze(ll& x, ll l, ll r) { ll res = 0; res += max(0LL, l - x); res += max(0LL, x - r); x = max(x, l); x = min(x, r); return res; } const int N = 2e5 + 2; int cnt[N][2]; void solve() { int n; cin >> n; ll ans = 0; for (int i = 0; i < n * 2; i++) { ll x, y; cin >> x >> y; x--, y--; ans += squeeze(x, 0, n - 1); ans += squeeze(y, 0, 1); cnt[x][y]++; } for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) { if (cnt[i][j] > 1) { int delta = min(cnt[i][j] - 1, 1 - cnt[i][j ^ 1]); delta = max(delta, 0); ans += delta; cnt[i][j] -= delta; cnt[i][j ^ 1] += delta; } } cnt[i + 1][0] += cnt[i][0] - 1; cnt[i + 1][1] += cnt[i][1] - 1; ans += abs(cnt[i][0] - 1); ans += abs(cnt[i][1] - 1); } cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; for (int tc = 1; tc <= T; tc++) { // cout << "Case #" << tc << ": "; solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...