Submission #506620

#	Time	Username	Problem	Language	Result	Execution time	Memory
506620		fcmalkcin	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	20 ms	25444 KiB

bridge

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

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

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define For(i,a,b) for (ll i=a;i<=b;i++)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e5+200;
const ll mod=1e9+7  ;
const ll base=3e18;

/// you will be the best but now you just are trash
/// goal 1/7


vector<ll> vt;
struct tk
{
    tk()
    {
        for (int i=0;i<4*maxn;i++)
        {
            st[i]=make_pair(0,0);
        }
    }
    pll st[4*maxn];
    pll mer(pll a,pll b)
    {
        return make_pair(a.ff+b.ff,a.ss+b.ss);
    }
    void update(ll id,ll left,ll right,ll x,ll diff)
    {
        if (x>right||x<left)
            return ;
        if (left==right)
        {
            st[id].ff+=diff;
            st[id].ss+=diff*(vt[left-1]);
            return ;
        }
        ll mid=(left+right)/2;
        update(id*2,left,mid,x,diff);
        update(id*2+1,mid+1,right,x,diff);
        st[id]=mer(st[id*2],st[id*2+1]);
    }
    pll get(ll id,ll left,ll right,ll x,ll y)
    {
        if (x>right||y<left) return make_pair(0,0);
        if (x<=left&&y>=right)
        {
            return st[id];
        }
        ll mid=(left+right)/2;
        return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
    }
    ll walk(ll id,ll left,ll right,ll val)
    {
        if (left==right) return left;
        ll mid=(left+right)/2;
        if (st[id*2].ss>=val) return walk(id*2,left,mid,val);
        else return walk(id*2+1,mid+1,right,val-st[id*2].ss);
    }
    ll getall(ll n)
    {
        pll h=st[1];
        ll sl=h.ff;
        if (sl==0) return 0;
        ll nw=sl/2;
        ll pos=walk(1,1,n,nw);
       // cout <<pos<<" "<<vt[pos-1]<<endl;
        auto p=get(1,1,n,1,pos);
        auto p1=get(1,1,n,pos,n);
        return p.ff*vt[pos-1]-p.ss-p1.ff*vt[pos-1]+p1.ss;
    }
};
bool lf(pll a,pll b)
{
    return (a.ff+a.ss<b.ff+b.ss);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll ans=0;
    ll k, n;
    cin>> k>> n;
    vector<pll> vt1;
    ll res=base;
    for (int i=1;i<=n;i++)
    {
        char p,p1;
        ll l, r;
        cin>> p>> l>> p1>> r;
        if (l>r) swap(l,r);

        if (p==p1)
        {
            ans+=(r-l);
        }
        else
        {
            ans++;
            vt.pb(l);
        vt.pb(r);
            vt1.pb(make_pair(l,r));
        }
    }
    sort(vt.begin(),vt.end());
    vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    sort(vt1.begin(),vt1.end(),lf);
    tk man;
    tk man1;
    ll len=vt.size();
    for (auto p:vt1)
    {
        ll l=lower_bound(vt.begin(),vt.end(),p.ff)-vt.begin()+1;
        ll r=lower_bound(vt.begin(),vt.end(),p.ss)-vt.begin()+1;
      //  cout <<l<<" "<<r<<" "<<len<<endl;
         man1.update(1,1,len,l,1);
        man1.update(1,1,len,r,1);
    }
    res=min(res,man1.getall(len)+ans);
    if (k==1)
    {
        cout<<res;
        return 0;
    }
   for (auto p:vt1)
    {
        ll l=lower_bound(vt.begin(),vt.end(),p.ff)-vt.begin()+1;
        ll r=lower_bound(vt.begin(),vt.end(),p.ss)-vt.begin()+1;
        man1.update(1,1,len,l,-1);
        man1.update(1,1,len,r,-1);
        man.update(1,1,len,l,1);
        man.update(1,1,len,r,1);
        res=min(res,man1.getall(len)+man.getall(len)+ans);
    }
    cout <<res<<endl;
}
/*2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7*/

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37