Submission #634351

#	Time	Username	Problem	Language	Result	Execution time	Memory
634351		Son	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	235 ms	255284 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define MAXN 200005

set < int > st;
vector < int > V;
int n,k,N;
int P[100000 + 5],S[100000 + 5], Q[100000 + 5], T[100000 + 5];
char inp[10];

vector < int > MS[MAXN * 2 + 5];
vector < int > VMS[MAXN * 2 + 5], CA[MAXN * 2 + 5], CB[MAXN * 2 + 5];
vector < LL > PA[MAXN * 2 + 5], PB[MAXN * 2 + 5];

vector < int > TA[MAXN * 2 + 5], TB[MAXN * 2 + 5], VA[MAXN * 2 + 5], VB[MAXN * 2 + 5];
vector < LL > A[MAXN * 2 + 5], B[MAXN * 2 + 5];

int mut( int a ){
    if ( a < 0 ) a = a * -1;
    return a;
}

int gv( int x ){
    if ( x > 1e9 + 1 ) return V.size()-1;
    return lower_bound(V.begin(),V.end(),x) - V.begin();
}

void upd( int p, int s, int e, int x, int v ){
    MS[p].pb(v);
    if ( s == e ) return;
    int m = ( s + e) >> 1;
    if ( x <= m ) upd(p+p+1,s,m,x,v);
    else upd(p+p+2,m+1,e,x,v);
}

void process( int p ){
    st.clear();
    for ( int id : MS[p] ){
        st.insert(S[id] + T[id]);
    }
    for ( int s : st ){
        VMS[p].pb(s);
        PA[p].pb(0);
        PB[p].pb(0);
        CA[p].pb(0);
        CB[p].pb(0);
    }
    for ( int id : MS[p] ){
        int pos = lower_bound(VMS[p].begin(),VMS[p].end(),S[id] + T[id]) - VMS[p].begin();
        CA[p][pos]++;
        CB[p][pos]++;
        PA[p][pos] += S[id];
        PB[p][pos] += T[id];
    }
    for ( int i = 1; i < VMS[p].size(); i++ ){
        CA[p][i] += CA[p][i-1];
        CB[p][i] += CB[p][i-1];
        PA[p][i] += PA[p][i-1];
        PB[p][i] += PB[p][i-1];
    }

    st.clear();
    for ( int id : MS[p] ){
        st.insert(T[id]);
    }
    for ( int s : st ){
        VB[p].pb(s);
        TB[p].pb(0);
        B[p].pb(0);
    }

    for ( int id : MS[p] ){
        int pos = lower_bound(VB[p].begin(),VB[p].end(), T[id]) - VB[p].begin();
        TB[p][pos]++;
        B[p][pos] += T[id];
    }

    for ( int i = 1; i < VB[p].size(); i++ ){
        TB[p][i] += TB[p][i-1];
        B[p][i] += B[p][i-1];
    }

    st.clear();
    for ( int id : MS[p] ){
        st.insert(S[id]);
    }
    for ( int s : st ){
        VA[p].pb(s);
        TA[p].pb(0);
        A[p].pb(0);
    }

    for ( int id : MS[p] ){
        int pos = lower_bound(VA[p].begin(),VA[p].end(), S[id]) - VA[p].begin();
        TA[p][pos]++;
        A[p][pos] += S[id];
    }

    for ( int i = 1; i < VA[p].size(); i++ ){
        TA[p][i] += TA[p][i-1];
        A[p][i] += A[p][i-1];
    }
}

void build( int p, int s, int e ){
    process(p);
    if ( s == e ){
        return;
    }  
    int m = ( s + e ) >> 1;
    build(p+p+1,s,m);
    build(p+p+2,m+1,e);
}

LL rmq_b( int p, int s, int e, int r ){
    if ( s > r ) return 0;
    if ( e <= r ){
        int pos = upper_bound(VB[p].begin(),VB[p].end(), V[r]) - VB[p].begin() - 1;
        LL sum = 0;

        if ( pos >= 0 ){
            sum += V[r] * 1LL * TB[p][pos] - B[p][pos];
            sum = sum + sum;
        }

        return sum;
    }
    int m = ( s + e ) >> 1;
    return rmq_b(p+p+1,s,m,r) + rmq_b(p+p+2,m+1,e,r);
}

LL rmq_bb( int p, int s, int e, int l, int r ){
    if ( s > r || e < l ) return 0;
    if ( l <= s && e <= r ){
        int pos = upper_bound(VB[p].begin(),VB[p].end(), V[r]) - VB[p].begin();
        LL sum = 0;
        if ( pos < VB[p].size() ){
            sum += B[p].back() - (pos==0?0:B[p][pos-1]);
            sum -= 1LL * V[r] * (TB[p].back() - (pos==0?0:TB[p][pos-1]));
        }
        return sum;
    }
}

LL rmq_a( int p, int s, int e, int l ){
    if ( e < l ) return 0;
    if ( l <= s ){
        int pos = lower_bound(VA[p].begin(),VA[p].end(),V[l]) - VA[p].begin();
        LL sum = 0;
        if ( pos < VA[p].size() ){
            sum += PA[p].back() - (pos == 0 ? 0 : PA[p][pos-1]) - 1LL * V[l] * (CA[p].back() - (pos==0?0:CA[p][pos-1]));
            sum += sum;
        }
        return sum;
    }
    int m = ( s + e ) >> 1;
    return rmq_a(p+p+1,s,m,l) + rmq_a(p+p+2,m+1,e,l);
}

LL rmq_ab( int p, int s, int e , int l, int r ){
    if ( s > r || e < l ) return 0;
    if ( l <= s && e <= r ){
        int lim = V[l] + V[r];
        LL sum = 0;
        int pos = upper_bound(VMS[p].begin(),VMS[p].end(), lim) - VMS[p].begin() - 1;

        if ( pos >= 0 ){
            sum += PA[p][pos] - 1LL * V[l] * (CA[p][pos]);
            sum = sum + sum;
        }
        return sum;
    }
    int m = ( s + e ) / 2;
    return rmq_ab(p+p+1,s,m,l,r) + rmq_ab(p+p+2,m+1,e,l,r);
}

LL rmq_ba( int p, int s, int e, int l, int r ){
    if ( s > r || e < l ) return 0;
    if ( l <= s && e <= r ){
        int lim = V[l] + V[r];
        LL sum = 0;
        int pos = upper_bound(VMS[p].begin(),VMS[p].end(), lim) - VMS[p].begin();

        if ( pos < VMS[p].size()){
            sum += 1LL * V[r] * (CB[p].back() - (pos == 0 ? 0 : CB[p][pos-1]));
            sum -= PB[p].back() - (pos==0?0:PB[p][pos-1]);
        }
        return sum;
    } 
    int m = ( s + e ) >> 1;
    return rmq_ba(p+p+1,s,m,l,r) + rmq_ba(p+p+2,m+1,e,l,r);
}

LL solve( int p1, int p2 ){
    LL ls = rmq_b(0,0,N,p1);
    LL rs = rmq_a(0,0,N,p2);
    LL ab = rmq_ab(0,0,N,p1,p2);
    LL ba = rmq_ba(0,0,N,p1,p2) - rmq_bb(0,0,N,p1,p2);
    //printf("%lld %lld %lld %lld = %d %d\n",ls,rs,ab,ba + ba,V[p1],V[p2]);
    return ls + rs + ab + ba + ba;
}

int main(){

    scanf("%d%d",&k,&n);
    LL ans = 1e18, sum = 0;
    for ( int i = 0; i < n; i++ ){
        scanf("%s%d",&inp,&S[i]);
        if ( inp[0] == 'A' ){
            P[i] = 0;
        } else {
            P[i] = 1;
        }

        scanf("%s%d",&inp,&T[i]);
        if ( inp[0] == 'A' ){
            Q[i] = 0;
        } else {
            Q[i] = 1;
        }
        // P[i] = 0;
        // Q[i] = 1;
        // S[i] = i;
        // T[i] = n - i;

        if ( S[i] > T[i] ) swap(S[i],T[i]);
        
        sum += T[i] - S[i];
        if ( P[i] != Q[i] ){
            st.insert(S[i]);
            st.insert(T[i]);
            sum++;
        }
    }

    st.insert(-1);
    st.insert(1e9 + 1);
    for ( int s : st ) V.pb(s);
    N = V.size()-1;

    for ( int i = 0; i < n; i++ ){
        if ( P[i] != Q[i] ){
            upd(0,0,N,gv(S[i]),i);
        }
    } 

    build(0,0,N);

    if ( k == 1 ){
        for ( int i = 0; i <= N; i++ ){
            LL temp = rmq_b(0,0,N,i) + rmq_a(0,0,N,i);
            if ( temp + sum < ans ) ans = temp + sum;
        }
    } else {
        int r = 0;
        for ( int i = 0; i < N; i++ ){
            if ( r <= i ) r = i + 1;
            while ( r + 1 <= N && solve(i,r) >= solve(i,r+1) ) r++;
            if ( solve(i,r) + sum < ans ) {
                ans = solve(i,r) + sum;
                //printf("%d %d = %lld+%lld = %lld\n",i,r,solve(i,r),sum,ans);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void process(int)':
bridge.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for ( int i = 1; i < VMS[p].size(); i++ ){
      |                      ~~^~~~~~~~~~~~~~~
bridge.cpp:80:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for ( int i = 1; i < VB[p].size(); i++ ){
      |                      ~~^~~~~~~~~~~~~~
bridge.cpp:101:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for ( int i = 1; i < VA[p].size(); i++ ){
      |                      ~~^~~~~~~~~~~~~~
bridge.cpp: In function 'long long int rmq_bb(int, int, int, int, int)':
bridge.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         if ( pos < VB[p].size() ){
      |              ~~~~^~~~~~~~~~~~~~
bridge.cpp: In function 'long long int rmq_a(int, int, int, int)':
bridge.cpp:152:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         if ( pos < VA[p].size() ){
      |              ~~~~^~~~~~~~~~~~~~
bridge.cpp: In function 'long long int rmq_ba(int, int, int, int, int)':
bridge.cpp:186:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         if ( pos < VMS[p].size()){
      |              ~~~~^~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:210:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
  210 |         scanf("%s%d",&inp,&S[i]);
      |                ~^    ~~~~
      |                 |    |
      |                 |    char (*)[10]
      |                 char*
bridge.cpp:217:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
  217 |         scanf("%s%d",&inp,&T[i]);
      |                ~^    ~~~~
      |                 |    |
      |                 |    char (*)[10]
      |                 char*
bridge.cpp: In function 'long long int rmq_bb(int, int, int, int, int)':
bridge.cpp:145:1: warning: control reaches end of non-void function [-Wreturn-type]
  145 | }
      | ^
bridge.cpp: In function 'int main()':
bridge.cpp:207:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |     scanf("%d%d",&k,&n);
      |     ~~~~~^~~~~~~~~~~~~~
bridge.cpp:210:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |         scanf("%s%d",&inp,&S[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         scanf("%s%d",&inp,&T[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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