Submission #914000

#	Time	Username	Problem	Language	Result	Execution time	Memory
914000		ace5	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	38 ms	6484 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int64_t top[n],bot[n];
    for(int i = 0;i < n;++i)
    {
        top[i] = 0;
        bot[i] = 0;
    }
    int64_t ans = 0;
    for(int i = 0;i < 2*n;++i)
    {
        int x,y;
        cin >> x >> y;
        int ind = 0;
        if(x <= 1)
            ind = 0;
        else if(x >= n)
            ind = n-1;
        else
            ind = x-1;
        ans += abs(x-(ind+1));
        if(y >= 2)
        {
            top[ind]++;
            ans += abs(y-2);
        }
        else
        {
            bot[ind]++;
            ans += abs(y-1);
        }
    }
   // cout << ans << ' ';
    int64_t f = 0,s = 0;
    for(int i = 0;i < n;++i)
    {
       // cout << top[i] << ' ' << bot[i] << ' ' << f << ' ' << s << "\n";
        if(f < i+1)
        {
            int64_t gl = min(i+1-f,top[i]);
            ans += (i-f)*gl -(gl-1)*gl/2;
            f += gl;
            top[i] -= gl;
        }
        if(s < i+1)
        {
            int64_t gl = min(i+1-s,bot[i]);
            ans += (i-s)*gl -(gl-1)*gl/2;
            s += gl;
            bot[i] -= gl;
        }
       // cout << top[i] << ' ' << bot[i] << ' ' << f << ' ' << s << "\n";
        if(bot[i] && top[i])
        {
            ans += bot[i] + top[i];
            bot[i+1] += bot[i];
            top[i+1] += top[i];
        }
        else if(top[i] && !bot[i])
        {
            int64_t gl = min(i+1-s,top[i]);
            ans += (i-s)*gl -(gl-1)*gl/2;
            s += gl;
            ans += gl;
            top[i] -= gl;
            ans += top[i];
            top[i+1] += top[i];
        }
        else if(!top[i] && bot[i])
        {
            int64_t gl = min(i+1-f,bot[i]);
            ans += (i-f)*gl -(gl-1)*gl/2;
            f += gl;
            ans += gl;
            bot[i] -= gl;
            ans += bot[i];
            bot[i+1] += bot[i];
        }
       // cout << ans << "\n";
    }
    cout << ans << "\n";
    return 0;
}

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