oj.uz

Submission #1089644

# Submission time Handle Problem Language Result Execution time Memory
1089644 2024-09-16T19:53:58 Z efishel Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

ll freq[100005][3];

// ii operator+ (const ii a, const ii b) { return ii{ a.first + b.first, a.second + b.second, }; }
// ii operator- (const ii a, const ii b) { return ii{ a.first - b.first, a.second - b.second, }; }
// ii operator+= (ii &a, const ii b) { return a = a + b; }
// ostream& operator<< (ostream &os, const ii a) { return os << a.first << ' ' << a.second; }

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n;
    vii ve(2*n);
    for (auto &[x, y] : ve) cin >> x >> y;
    ll ans = 0;
    auto fclamp = [&](ll l, ll r, ll &val) {
        if (val < l) { ans += l-val; val = l; }
        if (val > r) { ans += val-r; val = r; }
    };
    for (auto &[x, y] : ve) {
        fclamp(1, n, x);
        fclamp(1, 2, y);
        freq[x][y]++;
    }
    ll c1 = 0, c2 = 0; // ci = until the current prefix, how many free coins are in row i (negative to show lack of)
    for (ll i = 1; i <= n; i++) {
        c1 += freq[i][1]-1; // -1 = consumes one
        c2 += freq[i][2]-1; // -1 = consumes one
        // 4 cases, only in 2 we do something
        if (c1 < 0 && c2 > 0) { // shortage in c1 that's satisfied by c2
            // ll t = min(-c1, c2);
            ll t = 1;
            c1 += t; c2 -= t;
            ans += t;
        } else if (c2 < 0 && c1 > 0) { // vice versa
            // ll t = min(-c2, c1);
            ll t = 1;
            c2 += t; c1 -= t;
            ans += t;
        }
        // ans += abs(val) because if val is positive, #val coins have to move out, if val is negative, #-val coins have to eventually come in
        ans += abs(c1);
        ans += abs(c2);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 388 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 388 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 388 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 460 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -