oj.uz

Submission #171554

# Submission time Handle Problem Language Result Execution time Memory
171554 2019-12-29T07:32:24 Z Ruxandra985 Palembang Bridges (APIO15_bridge) C++14
22 / 100
 428 ms 31004 KB 
#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;
    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){
        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 {

    }
    return 0;
}

Compilation message

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9720 KB Output is correct
2 Correct 13 ms 9720 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 12 ms 9976 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 12 ms 9976 KB Output is correct
8 Correct 12 ms 9976 KB Output is correct
9 Correct 12 ms 9976 KB Output is correct
10 Correct 11 ms 9848 KB Output is correct
11 Correct 12 ms 9976 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 12 ms 9980 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct
6 Correct 11 ms 9876 KB Output is correct
7 Correct 12 ms 9976 KB Output is correct
8 Correct 12 ms 9976 KB Output is correct
9 Correct 12 ms 9976 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 11 ms 9976 KB Output is correct
12 Correct 54 ms 15768 KB Output is correct
13 Correct 428 ms 31004 KB Output is correct
14 Correct 141 ms 17008 KB Output is correct
15 Correct 197 ms 22136 KB Output is correct
16 Correct 55 ms 16272 KB Output is correct
17 Correct 163 ms 30992 KB Output is correct
18 Correct 162 ms 30456 KB Output is correct
19 Correct 318 ms 30456 KB Output is correct
20 Correct 58 ms 16752 KB Output is correct
21 Correct 198 ms 30708 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -