Submission #1180726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180726		user736482	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	26 ms	4060 KiB

joi2019_ho_t4

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099

ll n,q,s,t,a,b,c,d,ans,bst,k,e,m,pier,h,w,u;

ll l1[100007],l2[100007];
vector<ll>v,v2;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(ll i=0;i<2*n;i++){
        cin>>a>>b;
        ans+=abs(a-min(n,max(1LL,a)));
        if(b>1){
            ans+=b-2;
            v2.pb(min(n,max(1LL,a)));
            l2[min(n,max(1LL,a))]++;
        }
        else{
            ans-=b-1;
            v.pb(min(n,max(1LL,a)));
            l1[min(n,max(1LL,a))]++;
        }
    }
    for(ll i=1;i<=n;i++){
       // cout<<l1[i]<<" "<<l2[i]<<"\n";
    }//cout<<"\n\n";
    for(ll i=n;i>=1;i--){
        l1[i]--;
        l2[i]--;
       // cout<<ans<<" "<<l1[i]<<" "<<l2[i]<<"\n";
        if(l1[i]>0 && l2[i]<0){
            ans+=min(l1[i],-l2[i]);
            ll ak=min(l1[i],-l2[i]);
            l2[i]+=min(l1[i],-l2[i]);
            l1[i]-=ak;
        }
        if(l1[i]<0 && l2[i]>0){
            ans+=min(-l1[i],l2[i]);
            ll ak=min(-l1[i],l2[i]);
            l1[i]+=min(-l1[i],l2[i]);
            l2[i]-=ak;
        }
        if(l1[i]>0 || l2[i]>0){
            l1[i-1]+=l1[i];
            l2[i-1]+=l2[i];
            ans+=l1[i]+l2[i];
        }
        else{
            l1[i-1]+=l1[i];
            l2[i-1]+=l2[i];
            ans-=l1[i];
            ans-=l2[i];
        }
    }
    cout<<ans;
}

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