oj.uz

Submission #1109794

# Submission time Handle Problem Language Result Execution time Memory
1109794 2024-11-07T15:32:47 Z simona1230 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 124 ms 25636 KB 
#include <bits/stdc++.h>
using namespace std;
 
long long k,n,num;
pair<long long,long long> p[200001];
long long other,curr;
 
long long l[200001],r[200001];
vector<pair<long long,long long> > v;
long long c=0;
map<long long,long long> mp;
long long opp[200001];
int CNT;
 
void read()
{
    cin>>k>>n;
    for(long long i=1;i<=n;i++)
    {
        char c1,c2;
        long long s,f;
        cin>>c1>>s>>c2>>f;
        if(c1!=c2)
        {
            if(s>f)swap(s,f);
            curr+=s+f+1;
            v.push_back({s,1});
            v.push_back({f,2});
        }
        else
        {
            CNT++;
            other+=max(s,f)-min(s,f);
        }
    }
    sort(v.begin(),v.end());
 
    for(long long i=0;i<v.size();i++)
    {
        if(i==0||v[i].first!=v[i-1].first)c++;
        mp[v[i].first]=c;
        opp[c]=v[i].first;
        if(v[i].second==1)l[c]++;
        else r[c]++;
    }
}
 
void solve()
{
    //cout<<curr<<" "<<other<<endl;
    long long cntl=0,cntr=n-CNT,ans=curr+other;
    for(long long i=1;i<=c;i++)
    {
        curr+=(cntl-cntr)*2*(opp[i]-opp[i-1]);
        cntr-=l[i];
        cntl+=r[i];
        ans=min(ans,curr+other);
        //cout<<l[i]<<" "<<r[i]<<" "<<curr<<" "<<cntl<<" "<<cntr<<endl;
    }
    cout<<ans<<endl;
}
 
int main()
{
    read();
    solve();
    return 0;
}
 
/*
 1 5
 B 0 A 4
 B 1 B 3
 A 5 B 7
 B 2 A 6
 B 1 A 7
 
1 3
A 1 B 1
A 5 B 5
A 6 B 6
*/

Compilation message

bridge.cpp: In function 'void read()':
bridge.cpp:38:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(long long i=0;i<v.size();i++)
      |                       ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 6652 KB Output is correct
4 Correct 3 ms 6736 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 3 ms 6672 KB Output is correct
8 Correct 2 ms 6900 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 2 ms 6648 KB Output is correct
11 Correct 3 ms 6736 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 6480 KB Output is correct
4 Correct 3 ms 6736 KB Output is correct
5 Correct 3 ms 6736 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 3 ms 6736 KB Output is correct
8 Correct 3 ms 6736 KB Output is correct
9 Correct 3 ms 6736 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 36 ms 11608 KB Output is correct
13 Correct 124 ms 25516 KB Output is correct
14 Correct 66 ms 12464 KB Output is correct
15 Correct 72 ms 17336 KB Output is correct
16 Correct 51 ms 12340 KB Output is correct
17 Correct 104 ms 25636 KB Output is correct
18 Correct 100 ms 25264 KB Output is correct
19 Correct 123 ms 25012 KB Output is correct
20 Correct 59 ms 12468 KB Output is correct
21 Correct 104 ms 25264 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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