Submission #1054928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054928		KebabuVaikis15	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2073 ms	10704 KiB

bridge

///Gyvenimas grazus
#include <bits/stdc++.h>
using namespace std;

const int MAXN=100000;
long long k, n, pradSuma=0, suma=0;
char a[MAXN], b[MAXN];
long long x[MAXN], y[MAXN];

vector<tuple<long long, long long>> keliai;
long long dPtr=0;
long long dKairej=0, dDesinej;

vector<pair<long long, long long>> pertiltinesPoros;

long long skaiciuok(long long pos1, long long pos2)
{
    long long val=0;
    for (auto i:pertiltinesPoros)
    {
        if ((i.first<=pos1 && pos1<=i.second) ||
            (i.first<=pos2 && pos2<=i.second))
            continue;
        val+=2ll*min(min(abs(i.first-pos1), abs(i.second-pos1)), min(abs(i.first-pos2), abs(i.second-pos2)));
    }
    return val;
}

void tinkintDesine(long long id1, long long id2)
{
    while (dKairej<dDesinej)
    {
        long long pradPos=get<0>(keliai[dPtr]);
        dPtr++;
        suma-=2ll*(get<0>(keliai[dPtr])-pradPos)*(dDesinej-dKairej);
        if (get<1>(keliai[dPtr])==0)
            dDesinej--;
        else
            dKairej++;
    }
}

int main()
{
    cin>>k>>n;
    for (int i=0; i<n; i++)
    {
        cin>>a[i]>>x[i]>>b[i]>>y[i];
        if (x[i]>y[i])
            swap(x[i], y[i]);
        pradSuma+=y[i]-x[i];
        if (a[i]!=b[i])
        {
            pradSuma++;
            keliai.push_back(make_tuple(x[i], 0));
            keliai.push_back(make_tuple(y[i], 1));
            pertiltinesPoros.push_back({x[i], y[i]});
        }
    }
    keliai.push_back(make_tuple(0, 0));
    sort(keliai.begin(), keliai.end());
    if (keliai.size()==1)
    {
        cout<<pradSuma<<endl;
        return 0;
    }
    for (int i=0; i<n; i++)
        if (a[i]!=b[i])
            suma+=2ll*x[i];
    dDesinej=keliai.size()/2;
    tinkintDesine(-1, -1);
    if (k==1)
    {
        cout<<pradSuma+suma<<endl;
        return 0;
    }
    long long ats=LONG_MAX;
    for (int i=1; i<keliai.size(); i++)
        for (int j=i; j<keliai.size(); j++)
            ats=min(ats, pradSuma+skaiciuok(get<0>(keliai[i]), get<0>(keliai[j])));
    cout<<ats;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i=1; i<keliai.size(); i++)
      |                   ~^~~~~~~~~~~~~~
bridge.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int j=i; j<keliai.size(); j++)
      |                       ~^~~~~~~~~~~~~~

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