Submission #537576

#	Time	Username	Problem	Language	Result	Execution time	Memory
537576		kawaii	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	81 ms	7344 KiB

joi2019_ho_t4

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

int t, n, u, v, a[1000005], table[1000005][3], answer = 0, mod = 1e9 + 7;
string s;
mt19937_64 rng;

int mul(int x, int y){
    if(y == 0) return 1;
    int ans = mul(x, y / 2);
    if(y % 2 == 0) return (ans * ans) % mod;
    else return (((ans * ans) % mod) * x) % mod;
}

void solve(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 2; j++) table[i][j]--;
    }
    for(int i = 1; i <= n; i++){
        if(table[i - 1][1]) table[i][1] += table[i - 1][1];
        if(table[i - 1][2]) table[i][2] += table[i - 1][2];
        if(table[i][1] > 0 && table[i][2] < 0){
            int num = min(abs(table[i][1]), abs(table[i][2]));
            answer += num;
            table[i][1] -= num;
            table[i][2] += num;
        }
        else if(table[i][1] < 0 && table[i][2] > 0){
            int num = min(abs(table[i][1]), abs(table[i][2]));
            answer += num;
            table[i][1] += num;
            table[i][2] -= num;
        }
        answer += abs(table[i][1]) + abs(table[i][2]);
    }
    cout << answer;
}

signed main(){
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    rng.seed((int)main ^ time(0));
    #ifdef Kawaii
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    cin >> n;
    for(int i = 1; i <= n + n; i++){
        cin >> u >> v;
        if(1 <= u && u <= n && 1 <= v && v <= 2) table[u][v]++;
        else{
            if(1 <= u && u <= n){
                if(v > 2) table[u][2]++, answer += abs(v - 2);
                else table[u][1]++, answer += abs(v - 1);
            }
            else if(1 <= v && v <= 2){
                if(u > n) table[n][v]++, answer += abs(u - n);
                else table[1][v]++, answer += abs(u - 1);
            }
            else{
                int ans = abs(1 - u) + abs(1 - v);
                ans = min(ans, abs(n - u) + abs(1 - v));
                ans = min(ans, abs(1 - u) + abs(2 - v));
                ans = min(ans, abs(n - u) + abs(2 - v));
                if(ans == abs(1 - u) + abs(1 - v)) table[1][1]++;
                else if(ans == abs(n - u) + abs(1 - v)) table[n][1]++;
                else if(ans == abs(1 - u) + abs(2 - v)) table[1][2]++;
                else table[n][2]++;
                answer += ans;
            }
        }
    }
    solve();

    #ifdef Kawaii
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count(); 
        cout << "\n=====" << "\nUsed: " << duration << " ms\n";
    #endif
}

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