oj.uz

Submission #1054412

# Submission time Handle Problem Language Result Execution time Memory
1054412 2024-08-12T09:43:14 Z KebabuVaikis15 Palembang Bridges (APIO15_bridge) C++14
22 / 100
 65 ms 9668 KB 
#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++;
    ///Lyg tiesiog atsiranda vienas?
    ///Problemos cia?
//    cout<<"Pradedam "<<dPtr<<endl;
    while (kKairej<kDesinej)
    {
        long long pradPos=get<0>(keliai[kPtr]);
        kPtr++;
//        cout<<"K"<<kPtr<<endl;
//        cout<<dPtr<<endl;
//        cout<<suma<<"->";
        suma-=2ll*(get<0>(keliai[kPtr])-pradPos)*(kDesinej-kKairej);
//        cout<<suma<<endl;
        if (get<1>(keliai[kPtr])==0)
            kDesinej--;
        else
            kKairej++;
    }
}

void tinkintDesine(long long dPos)/////////////////////////////
{
    if (dPos<=get<0>(keliai[dPtr]))
        dKairej--;
    ///Problemos cia?
//    cout<<"Pradedam "<<dPtr<<endl;
    while (dKairej<dDesinej)
    {
        long long pradPos=get<0>(keliai[dPtr]);
        dPtr++;
//        cout<<dPtr;
        while(kairej[get<2>(keliai[dPtr])])
        {
//            cout<<", "<<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());
//    cout<<suma<<endl;
//    for (auto i:keliai)
//        cout<<get<0>(i)<<' '<<get<1>(i)<<' '<<get<2>(i)<<endl;
    for (int i=0; i<n; i++)
        if (a[i]!=b[i])
            suma+=2ll*(x[i]-get<0>(keliai[0]));
//    cout<<suma<<endl;
    ats=suma;
    dDesinej=keliai.size()/2;
    tinkintDesine(LONG_MAX);
    if (k==1)
    {
        cout<<suma<<endl;
        return 0;
    }
    while (vPtr!=2*n)
    {
        vPtr++;
        while (vPtr<2*n && get<1>(keliai[vPtr])!=0)
            vPtr++;
//        cout<<"V"<<vPtr<<endl;
        if (vPtr==2*n)
            break;
            ///Tiesiog pradinis, viskas tvarkoj?
        kairej[get<2>(keliai[vPtr])]=1;
        tinkintKaire(get<0>(keliai[vPtr]));
        tinkintDesine(y[get<1>(keliai[vPtr])]);
        ats=min(ats, suma);
    }
    cout<<ats<<endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 34 ms 8320 KB Output is correct
13 Correct 58 ms 7876 KB Output is correct
14 Correct 42 ms 9152 KB Output is correct
15 Correct 34 ms 4188 KB Output is correct
16 Correct 43 ms 9668 KB Output is correct
17 Correct 59 ms 9420 KB Output is correct
18 Correct 48 ms 8468 KB Output is correct
19 Correct 56 ms 9416 KB Output is correct
20 Correct 54 ms 8232 KB Output is correct
21 Correct 65 ms 9652 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -