제출 #171555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171555		Ruxandra985	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	399 ms	28744 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];
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;
    char c1 , c2;
    long long sol , base , sl , sr , sol_sl , sol_sr;
    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;
    sort (nv + 1 , nv + elem + 1);
    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
        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_sl = sol_sr = 2000000000000000;
        for (set <long long> :: iterator it = s.begin() ; it != s.end() ;){

            poz = (*it);
           // printf ("%lld ",poz);

            sol_sl = min(sol_sl , sl);
            sol_sr = min(sol_sr , 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_sl == 2000000000000000)
            sol_sl = 0;
        if (sol_sr == 2000000000000000)
            sol_sr = 0;
        fprintf (fout,"%lld" , sol_sl + sol_sr + base);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:34: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:39: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:41: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