Submission #1180740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180740		Szymon_Pilipczuk	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	104 ms	1984 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
int main()
{
    int n;
    cin>>n;
    vector<pair<int,int>> h(n,{0,0});
    vector<pair<int,int>> r(n+1,{1,1});
    ll ans = 0;
    for(int i =0 ;i<n*2;i++)
    {
        int x,y;
        cin>>x>>y;
        if(y >= 2)
        {
            ans += y-2;
            y = 2;
        }
        if(y <= 1)
        {
            ans+= 1-y;
            y = 1;
        }
        if(x > n)
        {
            ans+= x-n;
            x = n;
        }
        if(x < 1)
        {
            ans+=1-x;
            x = 1;
        }
        x--;
        if(y == 1)
        {
            h[x].st++;
        }
        else
        {
            h[x].nd++;
        }
    }
    //cout<<ans<<"\n";
    for(int i = 0;i<n;i++)
    {
        //cout<<h[i].st<<" "<<h[i].nd<<" "<<r[i].st<<" "<<r[i].nd<<"\n";
        if(r[i].st > h[i].st && r[i].nd > h[i].nd)
        {
            ans+= r[i].st - h[i].st + r[i].nd -h[i].nd;
            r[i+1].st += r[i].st-h[i].st;
            r[i+1].nd +=r[i].nd-h[i].nd;
        }
        else if(r[i].st <= h[i].st && r[i].nd <= h[i].nd)
        {
            ans+= h[i].st - r[i].st + h[i].nd -r[i].nd;
            h[i+1].st += h[i].st-r[i].st;
            h[i+1].nd +=h[i].nd-r[i].nd;
        }
        else if(r[i].st <= h[i].st && r[i].nd > h[i].nd)
        {
            int cu = h[i].st -r[i].st;
            ans += cu;
            if(r[i].nd-h[i].nd <= cu)
            {
                cu -= r[i].nd -h[i].nd;
                h[i+1].st += cu;
            }
            else
            {
                int cu2 = r[i].nd - h[i].nd;
                cu2 -= cu;
                ans+=cu2;
                r[i+1].nd += cu2;
            }
        }
        else
        {
            int cu = h[i].nd -r[i].nd;
            ans += cu;
            if(r[i].st-h[i].st <= cu)
            {
                cu -= r[i].st-h[i].st;
                h[i+1].nd += cu;
            }
            else
            {
                int cu2 = r[i].st - h[i].st;
                cu2 -= cu;
                ans+=cu2;
                r[i+1].st += cu2;
            }
        }
    }
    cout<<ans;

}

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