Submission #171576

#	Time	Username	Problem	Language	Result	Execution time	Memory
171576		Ruxandra985	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	351 ms	28820 KiB

bridge

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <long long> vmax[2*DIMN] , vmin[2*DIMN];
set <long long> s;
pair <long long,long long> nv[DIMN];
long long p[2*DIMN] , sol_sl[DIMN] , sol_sr[DIMN];
int cmp (pair <long long,long long> a , pair <long long,long long> b){
    return a.first + a.second < b.first + b.second; /// sort dupa media aritmetica
}
long long findd (long long x , long long tot){
    long long st , dr , mid;

    st = 0;
    dr = tot - 1;

    while (st <= dr){

        mid = (st + dr)/2;
        if (p[mid] == x)
            return mid;
        else if (p[mid] < x)
            st = mid + 1;
        else dr = mid - 1;

    }
    return -1;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long k , n , elem , tot = 0 , tot2 = 0, i ,p1 , p2 , left , right , poz , j;
    char c1 , c2;
    long long sol , base , sl , sr , sum , summ;
    fscanf (fin,"%lld%lld\n",&k,&n);
    base = 0;
    elem = 0;
    for (i=1;i<=n;i++){
        c1 = fgetc(fin);
        fscanf (fin,"%lld ",&p1);
        c2 = fgetc(fin);
        fscanf (fin,"%lld\n",&p2);
        if (c1 == c2){
            base = base + max ( p2 - p1 , p1 - p2 );
        }
        else{
            base = base + 1 + max ( p2 - p1 , p1 - p2 );

            nv[++elem] = make_pair(min(p1,p2) , max(p1,p2));
            p[tot++] = p1;
            p[tot++] = p2;

        }
    }
    sort ( p , p + tot);
    tot2 = 0;
    for (i=0;i<tot;i++){
        if (i == 0 || p[i] != p[i-1])
            p[tot2++] = p[i];
    }
    tot = tot2;
    for (i=1;i<=elem;i++){

        nv[i].first = findd (nv[i].first , tot);
        nv[i].second = findd (nv[i].second , tot);

        p1 = nv[i].first;
        p2 = nv[i].second;
        s.insert(p1);
        s.insert(p2);
        vmax[max(p1 ,p2)].push_back(min(p1 , p2));
        vmin[min(p1 ,p2)].push_back(max(p1 , p2));

    }
    n = elem;
    if (k == 1){ /// asta e ok
        left = 0;
        right = n - vmin[*(s.begin())].size();
        sl = 0;
        sr = 0;
        for (i=1;i<=n;i++){
            if (nv[i].first != *(s.begin()))
                sr = sr + 2 * ( p[nv[i].first] - p[(*(s.begin()))] );
        }
        sol = 2000000000000000;
        for (set <long long> :: iterator it = s.begin() ; it != s.end() ;){

            poz = (*it);
           // printf ("%lld ",poz);
            sol = min(sol , sl + sr);

            /// acum e timpul sa modific left ul si right ul

            left = left + vmax[poz].size();
            right = right - vmin[poz+1].size();

            it++;
            if (it == s.end())
                break;

            sl += 2 * (p[(*it)] - p[poz]) * left;
            sr -= 2 * (p[(*it)] - p[poz]) * ( right + vmin[poz+1].size() );

        }
        if (sol == 2000000000000000)
            sol = 0;
        fprintf (fout,"%lld" , sol + base);
    }
    else { /// aici k = 2

        /// construiesti pentru prefixe

        /// cand faci media primelor i , faci media dintre sumele intre inc si sf
        /// media aritmetica inc , inc+1 ... sf = media aritmetica inc sf

        sort (nv + 1 , nv + elem + 1 , cmp); /// sort dupa media aritmetica
        sum = 0;
        for (i=1;i<=elem;i++){ /// pt prefixul 1..i de pozitii , daca ai pune pod?

            sum = sum + nv[i].first + nv[i].second;

            poz = sum / (2 * i); /// media

            /// pt podurile 1 ... i cel mai bn e sa pui un pod aici

            /// calcul

            summ = 0;

            for (j=1;j<=i;j++){
                if (nv[i].first <= poz && poz <= nv[i].second)
                    continue;
                else if (nv[i].first < poz && nv[i].second < poz)
                    summ = summ + 2 * (poz - nv[i].second);
                else summ = summ + 2 * (nv[i].first - poz);
            }

            sol_sl[i] = summ;

            poz = poz + 1; /// inca o varianta de medie pt ca nu se imparte exact?

            /// calcul

            summ = 0;

            for (j=1;j<=i;j++){
                if (nv[i].first <= poz && poz <= nv[i].second)
                    continue;
                else if (nv[i].first < poz && nv[i].second < poz)
                    summ = summ + 2 * (poz - nv[i].second);
                else summ = summ + 2 * (nv[i].first - poz);
            }

            sol_sl[i] = min(sol_sl[i] , summ);

        }

        sum = 0;
        for (i=elem;i;i--){ /// pt prefixul 1..i de pozitii , daca ai pune pod?

            sum = sum + nv[i].first + nv[i].second;

            poz = sum / (2 * (elem - i + 1)); /// media

            /// pt podurile 1 ... i cel mai bn e sa pui un pod aici

            /// calcul

            summ = 0;

            for (j=n;j>i;j--){
                if (nv[i].first <= poz && poz <= nv[i].second)
                    continue;
                else if (nv[i].first < poz && nv[i].second < poz)
                    summ = summ + 2 * (poz - nv[i].second);
                else summ = summ + 2 * (nv[i].first - poz);
            }

            sol_sr[i] = summ;

            poz = poz + 1; /// inca o varianta de medie pt ca nu se imparte exact?

            /// calcul

            summ = 0;

            for (j=n;j>i;j--){
                if (nv[i].first <= poz && poz <= nv[i].second)
                    continue;
                else if (nv[i].first < poz && nv[i].second < poz)
                    summ = summ + 2 * (poz - nv[i].second);
                else summ = summ + 2 * (nv[i].first - poz);
            }

            sol_sr[i] = min(sol_sr[i] , summ);

        }

        /// conatruiesti pentru sufixe
        sol = 2000000000000;
        sol = min (sol_sl[elem] , sol_sr[1]);
        for (i = 1 ; i < elem ; i++){

            sol = min(sol , sol_sl[poz] + sol_sr[poz + 1]);

        }
        if (sol == 2000000000000)
            sol = 0;
        fprintf (fout,"%lld" , sol + base);
    }
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:37:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld\n",&k,&n);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:42:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld ",&p1);
         ~~~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:44:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld\n",&p2);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

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