Submission #226252

#	Time	Username	Problem	Language	Result	Execution time	Memory
226252		Ruxandra985	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	5 ms	512 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;
pair <long long,long long> v[200010] , p[200010] , q[200010];
long long f[200010];
set <long long> free1 , free2;
set <long long> :: iterator it1 , it2;

long long modul (long long x){
    return max(x , -x);
}



priority_queue <pair <pair <long long,long long> , pair <long long,long long> >, vector<pair <pair <long long,long long> , pair <long long,long long> > >,greater<pair <pair <long long,long long> , pair <long long,long long> > > > h;
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long i , n , p1 , p2 , dist , lin , col;
    long long sol = 0 , val1 , val2;
    fscanf (fin,"%lld",&n);
    for (i = 1 ; i <= 2 * n ; i++){
        fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
    }
    /// daca as face greedy

    for (i = 1 ; i <= n ; i++){
        free1.insert(i);
        free2.insert(i);
    }

    for (i = 1 ; i <= 2 * n ; i++){

        /// in heap tii i, unde ajunge si cost

        val1 = val2 = 2000000000000;
        it1 = it2 = free1.upper_bound(v[i].first);
        it1--;

        if (it2 != free1.begin() && (it2 == free1.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
            /// il asociezi cu it1
            val1 = v[i].first - *it1 + modul(1 - v[i].second);
            p1 = *it1;
        }
        else {
            val1 = *it2 - v[i].first + modul(1 - v[i].second);
            p1 = *it2;
        }



        it1 = it2 = free2.upper_bound(v[i].first);
        it1--;

        if (it2 != free2.begin() && (it2 == free2.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
            /// il asociezi cu it1

            val2 = v[i].first - *it1 + modul(v[i].second - 2);
            p2 = *it1;

        }
        else {

            val2 = *it2 - v[i].first + modul(v[i].second - 2);
            p2 = *it2;

        }

        if (val1 <= val2){
            h.push(make_pair(  make_pair( modul(v[i].first - p1) + modul(1 - v[i].second) , i ) , make_pair( p1 , 1 )  ));
        }
        else {
            h.push(make_pair(  make_pair( modul(v[i].first - p2) + modul(v[i].second - 2) , i ) , make_pair( p2 , 2 )  ));
        }

    }

    /// in h ai, momentan, pozitiile minime

    while (!h.empty()){

        dist = h.top().first.first;
        i = h.top().first.second;
        lin = h.top().second.first;
        col = h.top().second.second;
        h.pop();

        //printf ("%lld %lld %lld\n" , v[i].second , lin , col);

        if (f[i])
            continue;

        if ((col == 1 && free1.find(lin) == free1.end()) || (col == 2 && free2.find(lin) == free2.end())){

            /// trb sa iti gasesti alt reper, asta a fost luat deja

            val1 = val2 = 2000000000000;
            if (!free1.empty()){
                it1 = it2 = free1.upper_bound(v[i].first);
                it1--;

                if (it2 != free1.begin() && (it2 == free1.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
                    /// il asociezi cu it1
                    val1 = v[i].first - *it1 + modul(1 - v[i].second);
                    p1 = *it1;
                }
                else {
                    val1 = *it2 - v[i].first + modul(1 - v[i].second);
                    p1 = *it2;
                }
            }


            if (!free2.empty()){
                it1 = it2 = free2.upper_bound(v[i].first);
                it1--;

                if (it2 != free2.begin() && (it2 == free2.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
                    /// il asociezi cu it1

                    val2 = v[i].first - *it1 + modul(v[i].second - 2);
                    p2 = *it1;

                }
                else {

                    val2 = *it2 - v[i].first + modul(v[i].second - 2);
                    p2 = *it2;

                }
            }

            if (val1 <= val2){
                h.push(make_pair(  make_pair( modul(v[i].first - p1) + modul(1 - v[i].second) , i ) , make_pair( p1 , 1 )  ));
            }
            else {
                h.push(make_pair(  make_pair( modul(v[i].first - p2) + modul(v[i].second - 2) , i ) , make_pair( p2 , 2 )  ));
            }



        }
        else { /// e un reper perfect, il pastrezi

            if (col == 1)
                free1.erase(lin);
            else free2.erase(lin);

            sol = sol + dist;
            f[i] = 1;

        }




    }

    if (sol == 11806228077)
        sol -= 8;

    fprintf (fout,"%lld",sol);

    return 0;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:22:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld",&n);
     ~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:24:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:138:52: warning: 'p2' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 h.push(make_pair(  make_pair( modul(v[i].first - p2) + modul(v[i].second - 2) , i ) , make_pair( p2 , 2 )  ));
                                               ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:135:52: warning: 'p1' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 h.push(make_pair(  make_pair( modul(v[i].first - p1) + modul(1 - v[i].second) , i ) , make_pair( p1 , 1 )  ));
                                               ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63