Submission #754797

#	Time	Username	Problem	Language	Result	Execution time	Memory
754797		Kihihihi	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	86 ms	14348 KiB

joi2019_ho_t4

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

void solve()
{
    long long n;
    vector<pair<long long, long long>> v;
    cin >> n;
    v.resize(n * 2);
    for (long long i = 0; i < n * 2; i++)
    {
        cin >> v[i].first >> v[i].second;
    }

    long long ans = 0;
    for (long long i = 0; i < n * 2; i++)
    {
        if (v[i].second >= 2)
        {
            ans += v[i].second - 2;
            v[i].second = 2;
        }
        else
        {
            ans += 1 - v[i].second;
            v[i].second = 1;
        }

        if (v[i].first >= n)
        {
            ans += v[i].first - n;
            v[i].first = n;
        }
        else if (v[i].first <= 1)
        {
            ans += 1 - v[i].first;
            v[i].first = 1;
        }
    }

    vector<vector<long long>> a(2, vector<long long>(n)), b = a;
    for (long long i = 0; i < n * 2; i++)
    {
        v[i].first--; v[i].second--;
        a[1 - v[i].second][v[i].first]++;
    }
    for (long long i = 0; i < 2; i++)
    {
        for (long long j = 0; j < n; j++)
        {
            if (!a[i][j])
            {
                b[i][j] = 1;
            }
            else
            {
                a[i][j]--;
            }
        }
    }

    vector<long long> up, down;
    bool toa = false;
    for (long long i = 0; i < n; i++)
    {
        if (toa)
        {
            while (a[0][i])
            {
                up.push_back(i);
                a[0][i]--;
            }
            while (a[1][i])
            {
                down.push_back(i);
                a[1][i]--;
            }
        }
        else
        {
            while (b[0][i])
            {
                up.push_back(i);
                b[0][i]--;
            }
            while (b[1][i])
            {
                down.push_back(i);
                b[1][i]--;
            }
        }

        if (toa)
        {
            while (b[0][i] && up.size())
            {
                ans += i - up.back();
                up.pop_back();
                b[0][i]--;
            }
            while (b[1][i] && down.size())
            {
                ans += i - down.back();
                down.pop_back();
                b[1][i]--;
            }
            while (b[1][i] && up.size())
            {
                ans += i - up.back() + 1;
                up.pop_back();
                b[1][i]--;
            }
            while (b[0][i] && down.size())
            {
                ans += i - down.back() + 1;
                down.pop_back();
                b[0][i]--;
            }
        }
        else
        {
            while (a[0][i] && up.size())
            {
                ans += i - up.back();
                up.pop_back();
                a[0][i]--;
            }
            while (a[1][i] && down.size())
            {
                ans += i - down.back();
                down.pop_back();
                a[1][i]--;
            }
            while (a[1][i] && up.size())
            {
                ans += i - up.back() + 1;
                up.pop_back();
                a[1][i]--;
            }
            while (a[0][i] && down.size())
            {
                ans += i - down.back() + 1;
                down.pop_back();
                a[0][i]--;
            }
        }

        while (a[0][i])
        {
            up.push_back(i);
            toa = true;
            a[0][i]--;
        }
        while (a[1][i])
        {
            down.push_back(i);
            toa = true;
            a[1][i]--;
        }
        while (b[0][i])
        {
            up.push_back(i);
            toa = false;
            b[0][i]--;
        }
        while (b[1][i])
        {
            down.push_back(i);
            toa = false;
            b[1][i]--;
        }
    }
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

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