Submission #205468

#	Time	Username	Problem	Language	Result	Execution time	Memory
205468		anonymous	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	868 ms	262148 KiB

bridge

#include<iostream>
#include<utility>
#include<algorithm>
#define MAXN 100005
#define MAXD ((int) 1e9+5)
#define LL long long
#define fi first
#define se second
using namespace std;
int N, K, P, xi, yi;
LL ans, best=1LL<<60;
char s1, s2;
pair <LL, LL> Pt[MAXN];
class LazyCreate {
    LL ST[MAXN*120][4], P=2; //sum, num, l, r
public:
    void upd(int ind, int val, bool b, int l, int r, int cur) {
         if (l > ind || ind > r) {return;}
         if (l == r) {
            if (b) { //true means add
                ST[cur][0]+=val;
                ST[cur][1]++;
            } else {
                ST[cur][0]-=val;
                ST[cur][1]--;
            }
         } else {
            int mid=(l+r)>>1;
            if (!ST[cur][2]) {
                ST[cur][2]=P, ST[cur][3]=P+1, P+=2;
            }
            upd(ind, val, b, l, mid, ST[cur][2]);
            upd(ind, val, b, mid+1, r, ST[cur][3]);
            ST[cur][0]=ST[ST[cur][2]][0] + ST[ST[cur][3]][0];
            ST[cur][1]=ST[ST[cur][2]][1] + ST[ST[cur][3]][1];
         }
    }
    pair<LL,LL> ask(int lo, int hi, int l, int r, int cur) {
         if (hi < l || lo > r || cur == 0) {
            return(pair<LL,LL> {0,0});
         } else if (lo <= l && hi >= r) {
            return(pair<LL,LL> {ST[cur][0], ST[cur][1]});
         } else {
            int mid = (l+r)>>1;
            pair <LL,LL> res1 = ask(lo, hi, l, mid, ST[cur][2]);
            pair <LL,LL> res2 = ask(lo, hi, mid+1, r, ST[cur][3]);
            return(pair<LL,LL> {res1.fi + res2.fi, res1.se + res2.se});
         }
    }
    LL kth(int k, int l, int r, int cur) { //zero indexed
        if (l == r) {return(l);}
        int mid = (l + r)>>1;
        if (ST[ST[cur][2]][1] > k) {
            return(kth(k, l, mid, ST[cur][2]));
        } else {
            return(kth(k - ST[ST[cur][2]][1], mid+1, r, ST[cur][3]));
        }
    }
    LL Cost() {
        if (!ST[1][1]) {return(0);}
        LL med = kth(ST[1][1]/2, 0, MAXD, 1);
        pair<LL, LL> res1 = ask(0, med, 0, MAXD, 1);
        pair<LL, LL> res2 = ask(med+1, MAXD, 0, MAXD, 1);
        return(res1.se*med - res1.fi + res2.fi - res2.se*med);
    }
} Tl, Tr;

int main() {
    //freopen("palin.txt","r",stdin);
    scanf("%d %d",&K,&N);
    for (int i=0; i<N; i++) {
        scanf("\n%c %d %c %d", &s1, &xi, &s2, &yi);
        if (s1 == s2) {
            ans += abs(xi-yi);
        } else {
            ans+=1;
            Pt[P] = {xi,yi};
            P++;
        }
    }
    sort(Pt, Pt+P, [](pair<LL,LL> a, pair<LL,LL> b) {return(a.fi + a.se < b.fi + b.se);});
    for (int i=0; i<P; i++) {
            Tr.upd(Pt[i].fi, Pt[i].fi, true, 0, MAXD, 1);
            Tr.upd(Pt[i].se, Pt[i].se, true, 0, MAXD, 1);
    }
    if (K == 1) {
        printf("%lld\n", Tr.Cost() + ans);
    } else {
        best = Tr.Cost();
        for (int i=0; i<P; i++) {
            Tr.upd(Pt[i].fi, Pt[i].fi, false, 0, MAXD, 1);
            Tr.upd(Pt[i].se, Pt[i].se, false, 0, MAXD, 1);
            Tl.upd(Pt[i].fi, Pt[i].fi, true, 0, MAXD, 1);
            Tl.upd(Pt[i].se, Pt[i].se, true, 0, MAXD, 1);
            best = min(best, Tr.Cost() + Tl.Cost());
        }
        printf("%lld", best + ans);
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&K,&N);
     ~~~~~^~~~~~~~~~~~~~~
bridge.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c %d %c %d", &s1, &xi, &s2, &yi);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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