oj.uz

Submission #260856

# Submission time Handle Problem Language Result Execution time Memory
260856 2020-08-11T05:59:36 Z jeqcho Palembang Bridges (APIO15_bridge) C++17
31 / 100
 2000 ms 2456 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

vpi cross;

ll build(int bri)
{
    ll val=0;
    trav(e, cross)
    {
        val += (ll)(e.s-e.f+1);
        if(bri>e.s)
        {
            val += (ll)(bri - e.s) * (ll)2;
        }
        else if(bri<e.f)
        {
            val += (ll)(e.f - bri) * (ll)2;
        }
    }
    return val;
}

ll build2(int lb, int rb)
{
    ll val=0;
    ll lcand,rcand;
    trav(e, cross)
    {
        val += (ll)(e.s-e.f+1);
        lcand=rcand=0;
        if(lb>e.s)
        {
            lcand += (ll)(lb - e.s) * (ll)2;
        }
        else if(lb<e.f)
        {
            lcand += (ll)(e.f - lb) * (ll)2;
        }
        if(rb>e.s)
        {
            rcand += (ll)(rb - e.s) * (ll)2;
        }
        else if(rb<e.f)
        {
            rcand += (ll)(e.f - rb) * (ll)2;
        }
        val += min(lcand,rcand);
    }
    return val;
}

bool ok(int now)
{
    ll g = build(now+1) - build(now);
    if(g<0)return 1;
    else return 0;
}

bool check(int lb, int rb, int lef, int rig)
{
    if(lef)
    if(build2(lb+lef,rb+rig)-build2(lb,rb)<0)return 1;
    else return 0;
}

ll test(int lr, int rr)
{
    int rb = cross[rr].s;
    int lef = cross[lr].f;
    int rig = cross[lr].s;
    int mid;
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(check(mid, rb, 1,0))lef=mid+1;
        else rig=mid-1;
    }
    int lb = lef;
    lef = cross[rr].f;
    rig = cross[rr].s;
    while(lef<=rig)
    {
        mid=(lef+rig)/2;
        if(check(lb, mid, 0,1))lef=mid+1;
        else rig=mid-1;
    }
    rb = lef;
    ll ans=2e18;
    FOR(i,max(0,lb-5),min((int)1e9+1,lb+5))
    {
        FOR(j,max(0,rb-5),min((int)1e9+1,rb+5))
        {
            ans = min(ans, build2(lb,rb));
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int K,N;
    cin>>K>>N;
    char P[N],Q[N];
    int S[N],T[N];
    ll base=0;
    F0R(i,N)
    {
        cin>>P[i]>>S[i]>>Q[i]>>T[i];
        if(P[i]==Q[i])
        {
            base += (ll)( max(S[i],T[i]) - min(S[i],T[i]) );
        }
        else
        {
            cross.pb({min(S[i],T[i]), max(S[i],T[i])});
        }
    }
    ll ans;
    if(K==2)
    {
        ans = 2e14+5;
        sort(all(cross));
        F0R(i,sz(cross))
        {
            FOR(j,i+1,sz(cross))
            {
                ans=min(ans,test(i,j));
            }
        }
    }
    else
    {
        int lef=0,rig=1e9;
        int mid;
        while(lef<=rig)
        {
            mid=(lef+rig)/2;
            if(ok(mid))lef=mid+1;
            else rig=mid-1;
        }
        ans = 2e14+5;
        FOR(i,max(0,lef-10),min((int)1e9+1,lef+10))
        {
            ans=min(ans,build(i));
        }
    }
    if(ans==2e14+5)ans=0;
    ans+=base;
    cout<<ans<<'\n';
    return 0;
}

Compilation message

bridge.cpp: In function 'bool check(int, int, int, int)':
bridge.cpp:80:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if(lef)
       ^
bridge.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 31 ms 2172 KB Output is correct
13 Correct 92 ms 2456 KB Output is correct
14 Correct 52 ms 2172 KB Output is correct
15 Correct 51 ms 1556 KB Output is correct
16 Correct 38 ms 2172 KB Output is correct
17 Correct 48 ms 2172 KB Output is correct
18 Correct 43 ms 2288 KB Output is correct
19 Correct 80 ms 2172 KB Output is correct
20 Correct 68 ms 2172 KB Output is correct
21 Correct 75 ms 2288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 26 ms 384 KB Output is correct
4 Correct 150 ms 384 KB Output is correct
5 Correct 30 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 92 ms 384 KB Output is correct
8 Correct 200 ms 504 KB Output is correct
9 Correct 190 ms 384 KB Output is correct
10 Correct 145 ms 384 KB Output is correct
11 Correct 65 ms 384 KB Output is correct
12 Correct 141 ms 384 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 26 ms 392 KB Output is correct
4 Correct 154 ms 396 KB Output is correct
5 Correct 32 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 108 ms 384 KB Output is correct
8 Correct 204 ms 384 KB Output is correct
9 Correct 202 ms 384 KB Output is correct
10 Correct 150 ms 384 KB Output is correct
11 Correct 65 ms 384 KB Output is correct
12 Correct 140 ms 384 KB Output is correct
13 Execution timed out 2086 ms 384 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 26 ms 384 KB Output is correct
4 Correct 147 ms 384 KB Output is correct
5 Correct 30 ms 376 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 87 ms 388 KB Output is correct
8 Correct 199 ms 388 KB Output is correct
9 Correct 193 ms 392 KB Output is correct
10 Correct 151 ms 384 KB Output is correct
11 Correct 63 ms 384 KB Output is correct
12 Correct 140 ms 384 KB Output is correct
13 Execution timed out 2064 ms 384 KB Time limit exceeded
14 Halted 0 ms 0 KB -