Submission #45475

#	Time	Username	Problem	Language	Result	Execution time	Memory
45475		RayaBurong25_1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	370 ms	13796 KiB

bridge

#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#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, decS2;
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));
}
typedef struct se se;
struct se
{
    long long sum;
    int i;
};
bool operator<(se a, se b)
{
    return (a.sum < b.sum || (a.sum == b.sum && a.i < b.i));
}
std::map<se, int> SE;
std::map<se, int>::iterator p, q;
int main()
{
    int K, N;
    scanf("%d %d", &K, &N);
    int i, j, k;
    int i2, j2, k2;
    long long Obligatory = 0;
    long long Sum1a = 0, Sum1b = 0;
    long long Sum2a = 0, Sum2b = 0, Sum2c = 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);
    int On;
    if (K == 2)
    {
        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];
                SE[se{cEvent[incE[j].s] + cEvent[incE[j].e], incE[j].s}]--;
                decS2.push_back(incE[j]);
                std::sort(decS2.begin(), decS2.end(), sortDecS);
                j++;
            }
            while (k >= 0 && decS[k].s == i)
            {
                Sum1b -= cEvent[decS[k].s];
                k--;
            }
            j2 = 0;
            k2 = j - 1;
            p = SE.begin();
            Sum2a = 0;
            Sum2b = 0;
            Sum2c = 0;
            On = 0;
            for (i2 = 0; i2 < i; i2++)
            {
                Sum2a -= 2LL*j2;
                Sum2c += 2LL*On;
                while (p != SE.end() && p->first.sum < cEvent[i] + cEvent[i2])
                {
                    // printf("p %lld %d %d\n", p->first.sum, p->first.i, p->second);
                    if (k2 >= 0 && p->first.i >= decS2[k2].s)
                    {
                        p->second *= -1;
                        On += p->second;
                        Sum2c += 2LL*(cEvent[i] + cEvent[i2] - p->first.sum)*p->second;
                        // printf("Sum2c %lld\n", Sum2c);
                    }
                    p++;
                }
                while (k2 >= 0 && decS2[k2].s == i2)
                {
                    q = SE.find({cEvent[decS2[k2].s] + cEvent[decS2[k2].e], decS2[k2].s});
                    // printf("q %lld %d %d\n", q->first.sum, q->first.i, q->second);
                    if (q->second > 0)
                    {
                        Sum2c -= 2LL*(cEvent[i] + cEvent[i2] - q->first.sum)*q->second;
                        On -= q->second;
                        q->second *= -1;
                        // printf("Sum2c %lld\n", Sum2c);
                    }
                    // Sum2b += 2LL*(cEvent[i] - cEvent[decS2[k2].e]);
                    do
                    {
                        Sum2b += 2LL*(cEvent[i] - cEvent[decS2[k2].e]);
                        k2--;
                    } while (k2 >= 0 && decS2[k2].s == decS2[k2 + 1].s && decS2[k2].e == decS2[k2 + 1].e);
                }
                while (j2 < j && incE[j2].e < i2)
                {
                    Sum2b -= 2LL*(cEvent[i] - cEvent[incE[j2].e]);
                    Sum2a += 2LL*(cEvent[i] - cEvent[i2]);
                    j2++;
                }
                assert(Sum2a >= 0 && Sum2b >= 0 && Sum2c >= 0);
                // printf("i2 %d j2 %d k2 %d Sum1a %lld Sum1b %lld Sum2a %lld Sum2b %lld Sum2c %lld = %lld\n", i2, j2, k2, Sum1a, Sum1b, Sum2a, Sum2b, Sum2c, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)) - Sum2a - Sum2b - Sum2c);
                Ans = min(Ans, Obligatory + 2LL*(cEvent[i]*j - Sum1a) + 2LL*(Sum1b - cEvent[i]*(k + 1)) - Sum2a - Sum2b - Sum2c);
            }
            // printf("i %d j %d k %d Sum1a %lld Sum1b %lld = %lld\n", i, 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
    {
        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);
    }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:69: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:69: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:70: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:70: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:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < cEvent.size(); i++)
                     ~~^~~~~~~~~~~~~~~
bridge.cpp:182:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < cEvent.size(); i++)
                     ~~^~~~~~~~~~~~~~~
bridge.cpp:51: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:61: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