Submission #1021639

#TimeUsernameProblemLanguageResultExecution timeMemory
102163912345678Coin Collecting (JOI19_ho_t4)C++17
100 / 100
46 ms9808 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, p[nx][2], dp[nx][2], res;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=2*n; i++) 
    {
        cin>>p[i][0]>>p[i][1];
        if (!(1<=p[i][1]&&p[i][1]<=2))
        {
            if (p[i][1]<1) res+=1-p[i][1], p[i][1]=1;
            else res+=p[i][1]-2, p[i][1]=2;
        }
        if (!(1<=p[i][0]&&p[i][0]<=n))
        {
            if (p[i][0]<1) res+=1-p[i][0], p[i][0]=1;
            else res+=p[i][0]-n, p[i][0]=n;
        }
        dp[p[i][0]][p[i][1]-1]++;
    }
    for (int i=1; i<=n; i++)
    {
        dp[i][0]+=dp[i-1][0];
        res+=abs(dp[i-1][0]);
        dp[i][1]+=dp[i-1][1];
        res+=abs(dp[i-1][1]);
        dp[i][0]--;
        dp[i][1]--;
        while (dp[i][0]<0&&dp[i][1]>0) dp[i][0]++, dp[i][1]--, res++;
        while (dp[i][1]<0&&dp[i][0]>0) dp[i][1]++, dp[i][0]--, res++;
    }
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...