oj.uz

Submission #506647

# Submission time Handle Problem Language Result Execution time Memory
506647 2022-01-12T06:12:50 Z fcmalkcin Palembang Bridges (APIO15_bridge) C++17
100 / 100
 305 ms 31056 KB 
/*#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
{
    pll st[4*maxn];
    tk()
    {
        for (int i=0; i<4*maxn; i++)
        {
            st[i]=make_pair(0,0);
        }
    }

    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;
      //  cout <<id<<" "<<left<<" "<<right<<" "<<val<<" "<<st[id*2].ss<<" chk"<<endl;
        if (st[id*2].ff>=val)
            return walk(id*2,left,mid,val);
        else
            return walk(id*2+1,mid+1,right,val-st[id*2].ff);
    }
    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]<<" "<<sl<<" "<<nw<<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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25292 KB Output is correct
2 Correct 15 ms 25292 KB Output is correct
3 Correct 15 ms 25444 KB Output is correct
4 Correct 17 ms 25352 KB Output is correct
5 Correct 16 ms 25436 KB Output is correct
6 Correct 16 ms 25420 KB Output is correct
7 Correct 16 ms 25440 KB Output is correct
8 Correct 15 ms 25444 KB Output is correct
9 Correct 16 ms 25440 KB Output is correct
10 Correct 15 ms 25416 KB Output is correct
11 Correct 17 ms 25420 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25292 KB Output is correct
2 Correct 15 ms 25348 KB Output is correct
3 Correct 15 ms 25376 KB Output is correct
4 Correct 16 ms 25440 KB Output is correct
5 Correct 17 ms 25400 KB Output is correct
6 Correct 17 ms 25568 KB Output is correct
7 Correct 19 ms 25420 KB Output is correct
8 Correct 16 ms 25420 KB Output is correct
9 Correct 16 ms 25420 KB Output is correct
10 Correct 16 ms 25364 KB Output is correct
11 Correct 15 ms 25444 KB Output is correct
12 Correct 41 ms 28716 KB Output is correct
13 Correct 128 ms 28736 KB Output is correct
14 Correct 89 ms 28600 KB Output is correct
15 Correct 78 ms 27456 KB Output is correct
16 Correct 47 ms 28688 KB Output is correct
17 Correct 80 ms 28684 KB Output is correct
18 Correct 80 ms 28712 KB Output is correct
19 Correct 90 ms 28676 KB Output is correct
20 Correct 47 ms 28708 KB Output is correct
21 Correct 88 ms 28668 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25292 KB Output is correct
2 Correct 15 ms 25384 KB Output is correct
3 Correct 15 ms 25292 KB Output is correct
4 Correct 15 ms 25292 KB Output is correct
5 Correct 15 ms 25292 KB Output is correct
6 Correct 16 ms 25380 KB Output is correct
7 Correct 16 ms 25384 KB Output is correct
8 Correct 16 ms 25292 KB Output is correct
9 Correct 15 ms 25292 KB Output is correct
10 Correct 15 ms 25392 KB Output is correct
11 Correct 15 ms 25292 KB Output is correct
12 Correct 15 ms 25356 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25292 KB Output is correct
2 Correct 15 ms 25280 KB Output is correct
3 Correct 17 ms 25292 KB Output is correct
4 Correct 16 ms 25392 KB Output is correct
5 Correct 15 ms 25304 KB Output is correct
6 Correct 16 ms 25308 KB Output is correct
7 Correct 14 ms 25292 KB Output is correct
8 Correct 14 ms 25292 KB Output is correct
9 Correct 15 ms 25340 KB Output is correct
10 Correct 15 ms 25392 KB Output is correct
11 Correct 15 ms 25384 KB Output is correct
12 Correct 15 ms 25388 KB Output is correct
13 Correct 16 ms 25440 KB Output is correct
14 Correct 16 ms 25400 KB Output is correct
15 Correct 16 ms 25440 KB Output is correct
16 Correct 14 ms 25292 KB Output is correct
17 Correct 15 ms 25364 KB Output is correct
18 Correct 15 ms 25384 KB Output is correct
19 Correct 16 ms 25420 KB Output is correct
20 Correct 17 ms 25444 KB Output is correct
21 Correct 17 ms 25452 KB Output is correct
22 Correct 16 ms 25420 KB Output is correct
23 Correct 16 ms 25440 KB Output is correct
24 Correct 16 ms 25420 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25292 KB Output is correct
2 Correct 15 ms 25380 KB Output is correct
3 Correct 16 ms 25388 KB Output is correct
4 Correct 16 ms 25292 KB Output is correct
5 Correct 15 ms 25292 KB Output is correct
6 Correct 15 ms 25380 KB Output is correct
7 Correct 16 ms 25296 KB Output is correct
8 Correct 15 ms 25280 KB Output is correct
9 Correct 14 ms 25292 KB Output is correct
10 Correct 16 ms 25292 KB Output is correct
11 Correct 15 ms 25384 KB Output is correct
12 Correct 15 ms 25396 KB Output is correct
13 Correct 15 ms 25420 KB Output is correct
14 Correct 16 ms 25440 KB Output is correct
15 Correct 16 ms 25444 KB Output is correct
16 Correct 15 ms 25292 KB Output is correct
17 Correct 15 ms 25320 KB Output is correct
18 Correct 15 ms 25404 KB Output is correct
19 Correct 14 ms 25420 KB Output is correct
20 Correct 16 ms 25444 KB Output is correct
21 Correct 15 ms 25384 KB Output is correct
22 Correct 16 ms 25424 KB Output is correct
23 Correct 15 ms 25348 KB Output is correct
24 Correct 16 ms 25432 KB Output is correct
25 Correct 43 ms 28740 KB Output is correct
26 Correct 90 ms 28740 KB Output is correct
27 Correct 290 ms 28724 KB Output is correct
28 Correct 305 ms 31056 KB Output is correct
29 Correct 300 ms 31056 KB Output is correct
30 Correct 172 ms 28460 KB Output is correct
31 Correct 55 ms 30344 KB Output is correct
32 Correct 177 ms 31004 KB Output is correct
33 Correct 160 ms 30624 KB Output is correct
34 Correct 196 ms 31056 KB Output is correct
35 Correct 53 ms 30556 KB Output is correct
36 Correct 187 ms 30716 KB Output is correct
37 Correct 54 ms 29496 KB Output is correct