Submission #530534

#	Time	Username	Problem	Language	Result	Execution time	Memory
530534		Lobo	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	59 ms	6444 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

int n, ps1[maxn], ps2[maxn];

void solve() {
    cin >> n;
    int ans = 0;

    for(int i = 1; i <= 2*n; i++) {
        int x,y; cin >> x >> y;
        if(y > 2) {
            ans+= y-2;
            y = 2;
        }
        if(y < 1) {
            ans+= 1-y;
            y = 1;
        }
        
        if(x > n) {
            ans+= x-n;
            x = n;
        }
        if(x < 1) {
            ans+= 1-x;
            x = 1;
        }

        if(y == 1)
            ps1[x]++;
        else
            ps2[x]++;
    }

    for(int i = 1; i <= n; i++) {
        ps1[i]+= ps1[i-1];
        ps2[i]+= ps2[i-1];
        ps1[i]--;
        ps2[i]--;
        if(ps1[i] > 0 && ps2[i] < 0) {
            int ch = min(ps1[i],-ps2[i]);
            ans+= ch;
            ps1[i]-= ch;
            ps2[i]+=ch;
        }
        if(ps2[i] > 0 && ps1[i] < 0) {
            int ch = min(ps2[i],-ps1[i]);
            ans+= ch;
            ps2[i]-= ch;
            ps1[i]+=ch;
        }

        ans+= abs(ps1[i]);
        ans+= abs(ps2[i]);
    }

    cout << ans << endl;




}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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