oj.uz

Submission #1054349

# Submission time Handle Problem Language Result Execution time Memory
1054349 2024-08-12T09:00:09 Z KebabuVaikis15 Palembang Bridges (APIO15_bridge) C++14
22 / 100
 61 ms 9664 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, long long dPos)
//{////////////////////////////////////////////////////////////
//    if (dPos<=get<0>(keliai[kPtr]))
//        kKairej++;
//    if (kPos>=get<0>(keliai[kPtr]))
//        kDesinej++;
//    while (kKairej<kDesinej)
//    {
//        long long pradPos=get<0>(keliai[kPtr]);
//        kPtr++;
//        while(kairej[get<2>(keliai[kPtr])])
//            kPtr++;
//        ats-=(pradPos-get<0>(keliai[kPtr]))*(kDesinej-kKairej);
//        if (get<1>(keliai[kPtr])==0)
//            kDesinej--;
//        else
//            kKairej++;
//    }
//}

void tinkintDesine(long long dPos)/////////////////////////////
{
    if (dPos<=get<0>(keliai[dPtr]))
        dKairej--;
//    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<<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++;



//        tinkintKaire(0); //////////////
        tinkintDesine(0); ////////////////'
    }
    cout<<ats<<endl;
}

Subtask #1
8.0 / 8.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 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 0 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

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 1 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 480 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 35 ms 8396 KB Output is correct
13 Correct 58 ms 8524 KB Output is correct
14 Correct 42 ms 8644 KB Output is correct
15 Correct 34 ms 4812 KB Output is correct
16 Correct 43 ms 8796 KB Output is correct
17 Correct 59 ms 8980 KB Output is correct
18 Correct 47 ms 9664 KB Output is correct
19 Correct 61 ms 8444 KB Output is correct
20 Correct 53 ms 9664 KB Output is correct
21 Correct 53 ms 8136 KB Output is correct

Subtask #3
0 / 9.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 -

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 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.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 348 KB Output isn't correct
4 Halted 0 ms 0 KB -