Submission #1106521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106521		iloveadhoc	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	33 ms	8008 KiB

joi2019_ho_t4

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

#define int long long
#define N 200005

int n, sum[3][N];

signed main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n;
    int res = 0;
    
    for (int i = 1; i <= 2 * n; i++){
        int x, y;
        cin >> x >> y;
        if (x < 1) {res += 1 - x; x = 1;}
        if (x > n) {res += x - n; x = n;}
        if (y < 1) {res += 1 - y; y = 1;}
        if (y > 2) {res += y - 2; y = 2;}
        sum[y][x]++;
    }
    
    for (int i = 1; i <=  n; i++){
        sum[1][i] += sum[1][i - 1] - 1;
        sum[2][i] += sum[2][i - 1] - 1;
        for (int j = 1; j <= 2; j++){
            if (sum[j][i] > 0 && sum[3 ^ j][i] < 0){
                int tmp = min(sum[j][i], -sum[3 ^ j][i]);
                sum[j][i] -= tmp;
                res += tmp;
                sum[3 ^ j][i] += tmp;
            }  
        } 
            res += abs(sum[1][i]);
            res += abs(sum[2][i]);
    }
    
    cout << res;
    
    return 0;
}

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