Submission #45467

#	Time	Username	Problem	Language	Result	Execution time	Memory
45467		RayaBurong25_1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	338 ms	13908 KiB

bridge

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#define INF 1000000000000000000LL
typedef struct node node;
struct node
{
    int s, e;
};
std::set<long long> Event;
std::vector<long long> cEvent;
std::vector<node> incE, decS;
long long abs(long long a)
{
    return (a < 0)?-a:a;
}
long long min(long long a, long long b)
{
    return (a < b)?a:b;
}
long long max(long long a, long long b)
{
    return (a > b)?a:b;
}
int sortIncE(node a, node b)
{
    return (a.e < b.e || (a.e == b.e && a.s < b.s));
}
int sortDecS(node a, node b)
{
    return (a.s > b.s || (a.s == b.s && a.e > b.e));
}
int main()
{
    int K, N;
    scanf("%d %d", &K, &N);
    int i, j, k;
    long long Obligatory = 0;
    long long Sum1a = 0, Sum1b = 0, Sum2 = 0;
    char P, Q;
    int S, T;
    for (i = 0; i < N; i++)
    {
        scanf(" %c %d %c %d", &P, &S, &Q, &T);
        if (P == Q)
        {
            Obligatory += abs(T - S);
        }
        else
        {
            Obligatory += 1 + abs(T - S);
            incE.push_back({min(S, T), max(S, T)});
            decS.push_back({min(S, T), max(S, T)});
            Event.insert(S);
            Event.insert(T);
        }
    }
    // printf("Obligatory %lld\n", Obligatory);
    std::set<long long>::iterator it;
    for (it = Event.begin(); it != Event.end(); it++)
    {
        cEvent.push_back(*it);
        // printf("cEvent %lld\n", *it);
    }
    N = incE.size();
    for (i = 0; i < N; i++)
    {
        S = std::lower_bound(cEvent.begin(), cEvent.end(), incE[i].s) - cEvent.begin();
        T = std::lower_bound(cEvent.begin(), cEvent.end(), incE[i].e) - cEvent.begin();
        incE[i] = {S, T};
        S = std::lower_bound(cEvent.begin(), cEvent.end(), decS[i].s) - cEvent.begin();
        T = std::lower_bound(cEvent.begin(), cEvent.end(), decS[i].e) - cEvent.begin();
        decS[i] = {S, T};
        // printf("S%d T%d\n", S, T);
        Sum1b += cEvent[S];
    }
    std::sort(incE.begin(), incE.end(), sortIncE);
    std::sort(decS.begin(), decS.end(), sortDecS);

    if (K == 1)
    {
        long long Ans = INF;
        if (cEvent.size() == 0)
            Ans = Obligatory;
        j = 0;
        k = N - 1;
        for (i = 0; i < cEvent.size(); i++)
        {
            while (j < N && incE[j].e < i)
            {
                Sum1a += cEvent[incE[j].e];
                j++;
            }
            while (k >= 0 && decS[k].s == i)
            {
                Sum1b -= cEvent[decS[k].s];
                k--;
            }
            // printf("j %d k %d Sum1a %lld Sum1b %lld = %lld\n", j, k, Sum1a, Sum1b, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)));
            Ans = min(Ans, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)));
        }
        printf("%lld", Ans);
    }
    else
    {
        //not yet
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:53:32: warning: narrowing conversion of 'min(((long long int)S), ((long long int)T))' from 'long long int' to 'int' inside { } [-Wnarrowing]
             incE.push_back({min(S, T), max(S, T)});
                             ~~~^~~~~~
bridge.cpp:53:43: warning: narrowing conversion of 'max(((long long int)S), ((long long int)T))' from 'long long int' to 'int' inside { } [-Wnarrowing]
             incE.push_back({min(S, T), max(S, T)});
                                        ~~~^~~~~~
bridge.cpp:54:32: warning: narrowing conversion of 'min(((long long int)S), ((long long int)T))' from 'long long int' to 'int' inside { } [-Wnarrowing]
             decS.push_back({min(S, T), max(S, T)});
                             ~~~^~~~~~
bridge.cpp:54:43: warning: narrowing conversion of 'max(((long long int)S), ((long long int)T))' from 'long long int' to 'int' inside { } [-Wnarrowing]
             decS.push_back({min(S, T), max(S, T)});
                                        ~~~^~~~~~
bridge.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < cEvent.size(); i++)
                     ~~^~~~~~~~~~~~~~~
bridge.cpp:40:37: warning: unused variable 'Sum2' [-Wunused-variable]
     long long Sum1a = 0, Sum1b = 0, Sum2 = 0;
                                     ^~~~
bridge.cpp:37: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:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %c %d", &P, &S, &Q, &T);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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