Submission #773274

#	Time	Username	Problem	Language	Result	Execution time	Memory
773274		Sami_Massah	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	72 ms	15380 KiB

joi2019_ho_t4

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


const long long maxn = 2e5 + 12, mod = 1e9 + 7;
long long n, a[3][maxn], x[maxn], y[maxn];
set <int> Q[3];
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i = 0; i < 2 * n; i++)
        cin >> x[i] >> y[i];
    long long d = 0;
    for(int i = 0; i < 2 * n; i++){
        if(y[i] < 1 || 2 < y[i]){
            if(y[i] < 1){
                d += 1 - y[i];
                y[i] = 1;
                }
            else{
                d += y[i] - 2;
                y[i] = 2;
            }
        }
        if(x[i] < 1 || n < x[i]){
            if(x[i] < 1){
                d += 1 - x[i];
                x[i] = 1;
            }
            else{
                d += x[i] - n;
                x[i] = n;
            }
        }
        a[y[i]][x[i]] += 1;
    }
    long long ans = 0;
 /*   cout << endl;
    for(int i = 1; i <= n; i++)
        cout << a[1][i] << ' ';
    cout << endl;
    for(int i = 1; i <= n; i++)
        cout << a[2][i] << ' ';
    cout << endl;*/
    for(int i = 1; i <= n; i++){
        if(a[1][i] == 0)
            Q[1].insert(i);
        if(a[2][i] == 0){
            Q[2].insert(i);
            }
        while(a[1][i] > 1 && Q[1].size()){
            ans += abs(*Q[1].begin() - i);
            a[1][i] -= 1;
            Q[1].erase(Q[1].begin());
        }

        while(a[2][i] > 1 && Q[2].size()){

            ans += abs(*Q[2].begin() - i);
            a[2][i] -= 1;
            Q[2].erase(Q[2].begin());
        }

        while(a[1][i] > 1 && Q[2].size()){

            ans += abs(*Q[2].begin() - i) + 1;
            a[1][i] -= 1;
            Q[2].erase(Q[2].begin());
        }
        while(a[2][i] > 1 && Q[1].size()){
            ans += abs(*Q[1].begin() - i) + 1;
            a[2][i] -= 1;
            Q[1].erase(Q[1].begin());
        }

        while(a[1][i] > 1){
            a[1][i + 1] += 1;
            ans += 1;
            a[1][i] -= 1;
        //    cout << i << endl;
        }
        while(a[2][i] > 1){
            a[2][i + 1] += 1;
            ans += 1;
            a[2][i] -= 1;
        }
    }
    cout << ans + d << endl;
}

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