Submission #1055009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055009		KebabuVaikis15	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	86 ms	9584 KiB

bridge

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

const int MAXN=100000;
long long k, n, suma=0, ats=LONG_MAX;
char a[MAXN], b[MAXN];
long long x[MAXN], y[MAXN];
vector<tuple<long long, long long, long long>> keliai;
long long kPtr=0, vPtr=1, dPtr=0;
long long kKairej=0, kDesinej=0, dKairej=0, dDesinej;
bool kairej[MAXN];

void tinkintKaire(long long kPos)
{
    suma+=2ll*(kPos-get<0>(keliai[kPtr]));
    kDesinej++;
    while (kKairej<kDesinej)
    {
        long long pradPos=get<0>(keliai[kPtr]);
        kPtr++;
        suma-=2ll*(get<0>(keliai[kPtr])-pradPos)*(kDesinej-kKairej);
        if (get<1>(keliai[kPtr])==0)
            kDesinej--;
        else
            kKairej++;
    }
}

void tinkintDesine(long long dPos)
{
    if (dPos<=get<0>(keliai[dPtr]))
        dKairej--;
    while (dKairej<dDesinej)
    {
        long long pradPos=get<0>(keliai[dPtr]);
        dPtr++;
        while(kairej[get<2>(keliai[dPtr])])
            dPtr++;
//        cout<<"D"<<dPtr<<endl;
//        cout<<endl;
//        cout<<suma<<"->";
        suma-=2ll*(get<0>(keliai[dPtr])-pradPos)*(dDesinej-dKairej);
//        cout<<suma<<endl;
        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]);
        suma+=y[i]-x[i];
        if (a[i]!=b[i])
        {
            suma++;
            keliai.push_back(make_tuple(x[i], 0, i));
            keliai.push_back(make_tuple(y[i], 1, i));
        }
    }
    keliai.push_back(make_tuple(0, 0, 0));
    sort(keliai.begin(), keliai.end());
    if (keliai.size()==1)
    {
        cout<<suma<<endl;
        return 0;
    }
    for (int i=0; i<n; i++)
        if (a[i]!=b[i])
            suma+=2ll*(x[i]-get<0>(keliai[0]));
    ats=suma;
    dDesinej=keliai.size()/2;
    tinkintDesine(LONG_MAX);
    if (k==1)
    {
        cout<<suma<<endl;
        return 0;
    }
    while (vPtr!=keliai.size())
    {
        vPtr++;
        while (vPtr<keliai.size() && get<1>(keliai[vPtr])!=0)
            vPtr++;
//        cout<<"V"<<vPtr<<endl;
        if (vPtr==keliai.size())
            break;
        kairej[get<2>(keliai[vPtr])]=1;
        tinkintKaire(get<0>(keliai[vPtr]));
        tinkintDesine(y[get<1>(keliai[vPtr])]);
        ats=min(ats, suma);
    }
    cout<<ats<<endl;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:85:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     while (vPtr!=keliai.size())
      |            ~~~~^~~~~~~~~~~~~~~
bridge.cpp:88:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         while (vPtr<keliai.size() && get<1>(keliai[vPtr])!=0)
      |                ~~~~^~~~~~~~~~~~~~
bridge.cpp:91:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if (vPtr==keliai.size())
      |             ~~~~^~~~~~~~~~~~~~~

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