Submission #1054760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054760		FaustasK	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	104 ms	11712 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

struct gyventojas
{
    char p;
    double s;
    char q;
    double t;
};

const int maxn = 100000;
const long long daug = 1000000000000000;

int k, n, kiek;
gyventojas M[maxn];

vector <int> reikalingi;
vector <int> nereikalingi;
vector <int> medianai;
vector <int> unikalus;
set <int> buvo;

long long skaiciuok_keliu_suma(int tiltas1, int tiltas2)
{
    long long ats = 0;
    if(kiek>0)
    {
        if(k == 1)
        {
            for(int i = 0; i<reikalingi.size(); i++)
            {
                int j = reikalingi[i];
                ats += abs(M[j].s - tiltas1) + abs(M[j].t - tiltas1);
            }
        }
        else
        {
            for(int f = 0; f<reikalingi.size(); f++)
            {
                int x = reikalingi[f];
                int a1 = abs(M[x].s - tiltas1) + abs(M[x].t - tiltas1);
                int a2 = abs(M[x].s - tiltas2) + abs(M[x].t - tiltas2);
                ats += min(a1, a2);
            }
        }
    }
    for(int i = 0; i<nereikalingi.size(); i++)
    {
        int j = nereikalingi[i];
        ats += abs(M[j].s - M[j].t);
    }
    return ats + reikalingi.size();
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> k >> n;
    pair<double, int> st2[n];
    int j = 0;
    for(int i = 0; i<n; i++)
    {
        cin >> M[i].p >> M[i].s >> M[i].q >> M[i].t;
        if(M[i].p != M[i].q)
        {
            //cout << i << endl;
            medianai.push_back(M[i].s);
            medianai.push_back(M[i].t);
            st2[j++] = {(M[i].s+M[i].t)/2, i};
            reikalingi.push_back(i);
        }
        else nereikalingi.push_back(i);
    }
    /*for(int i = 0; i<reikalingi.size(); i++)
    {
        cout << st2[i].first << ' ' << st2[i].second << endl;
    }
    cout << st2[0].second << ' ' << st2[1].second;*/
    sort(medianai.begin(), medianai.end());
    kiek = reikalingi.size();

    if(k==1)
    {
        if(kiek > 0) cout << skaiciuok_keliu_suma(medianai[medianai.size()/2], -1);
        else cout << skaiciuok_keliu_suma(-1, -1);
    }
    else
    {
        long long galats = 0;
        if(kiek > 0)
        {
            galats = daug;
            n = reikalingi.size();
            sort(st2, st2+n);
            long long sumos_kaire[n-1];
            long long sumos_desine[n-1];
             ///i kaire puse
             priority_queue <int> q1;
             priority_queue <int> q2;
             long long s1 = 0;
             long long s2 = 0;

             int s = M[st2[0].second].s;
             int t = M[st2[0].second].t;
             //cout << '[' << st2[0].second+1 << endl;

             if(s>t) swap(s, t);
             q1.push(s);
             q2.push(-t);
             s1 += s;
             s2 += t;
             sumos_kaire[0] = -s1+s2;
             //cout << sumos_kaire[0] << ' ';
             //cout << ']' << s1 << ' ' << s2 << endl;

             for(int i = 1; i<n-1; i++)
             {
                 //cout << '[' << st2[i].second+1 << endl;

                 if(q2.top() > 0) cout << i << "#############\n";
                 s = M[st2[i].second].s;
                 t = M[st2[i].second].t;
                 if(s>t) swap(s,t);
                 if(s <= -q2.top() && t >= q1.top())
                 {
                     //cout << '!';
                     q1.push(s);
                     q2.push(-t);
                     s1 += s;
                     s2 += t;
                     //cout << s1 << ' ' << s2 << endl;
                 }
                 else if(t < q1.top())
                 {
                     //cout << '?';
                     q2.push(-q1.top());
                     s2 += q1.top();
                     s1 -= q1.top();
                     q1.pop();
                     q1.push(s);
                     q1.push(t);
                     s1+= t+s;
                 }
                 else if(s > -q2.top())
                 {
                     //cout << '/';
                     if(-q2.top() < 0) cout << "@@@@@@@@@@@@@@";
                     q1.push(-q2.top());
                     s1 += -q2.top();
                     s2 -= -q2.top();
                     q2.pop();
                     q2.push(-s);
                     q2.push(-t);
                     s2+= t+s;
                 }
                 sumos_kaire[i] = -s1+s2;
                 //if(i == n-2) cout << '{' << s1 << ' ' << s2 << endl;
                 //cout << sumos_kaire[i] << ' ';
             }
             /// desine puse
             while(!q1.empty())q1.pop();
             while(!q2.empty())q2.pop();
             s1 = 0;
             s2 = 0;

             s = M[st2[n-1].second].s;
             t = M[st2[n-1].second].t;

             //cout << "!!!!!!" << st2[n-1].first << endl;
             if(s>t) swap(s, t);
             q1.push(s);
             q2.push(-t);
             s1 += s;
             s2 += t;
             sumos_desine[n-2] = -s1+s2;
             //cout << sumos_desine[n-2] << ' ';
             //cout << ']' << s1 << ' ' << s2 << endl;

             for(int i = n-2; i>=1; i--)
             {
                 //cout << "!!!!!!" << st2[i].first << endl;
                 s = M[st2[i].second].s;
                 t = M[st2[i].second].t;
                 if(s>t) swap(s,t);
                 if(s <= -q2.top() && t >= q1.top())
                 {
                     //cout << '!';
                     q1.push(s);
                     q2.push(-t);
                     s1 += s;
                     s2 += t;
                     //cout << s1 << ' ' << s2 << endl;
                 }
                 else if(t < q1.top())
                 {
                     //cout << '?';
                     q2.push(-q1.top());
                     s2 += q1.top();
                     s1 -= q1.top();
                     q1.pop();
                     q1.push(s);
                     q1.push(t);
                     s1+= t+s;
                 }
                 else if(s > -q2.top())
                 {
                     //cout << '/';
                     q1.push(-q2.top());
                     s1 += -q2.top();
                     s2 -= -q2.top();
                     q2.pop();
                     q2.push(s);
                     q2.push(t);
                     s2+= t+s;
                 }
                 sumos_desine[i-1] = -s1+s2;
                 //cout << sumos_desine[i-1] << ' ';
             }
             for(int i = 0; i<n-1; i++)
             {
                 galats = min(galats, sumos_kaire[i] + sumos_desine[i]);
             }
         }
         for(int i = 0; i<nereikalingi.size(); i++)
         {
             int j = nereikalingi[i];
             galats += abs(M[j].s - M[j].t);
         }
         cout << galats + reikalingi.size();
    }
    return 0;
}
/*
2 4
A 1 B 6
A 5 B 3
A 8 B 7
A 10 B 10





2 2
A 10 B 5
A 1 B 1

2 3
A 10 B 5
A 6 B 8
A 1 B 1

2 4
A 10 B 5
A 6 B 8
A 3 B 4
A 1 B 1
*/

Compilation message (stderr)

bridge.cpp: In function 'long long int skaiciuok_keliu_suma(int, int)':
bridge.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int i = 0; i<reikalingi.size(); i++)
      |                            ~^~~~~~~~~~~~~~~~~~
bridge.cpp:40:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for(int f = 0; f<reikalingi.size(); f++)
      |                            ~^~~~~~~~~~~~~~~~~~
bridge.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i<nereikalingi.size(); i++)
      |                    ~^~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:226:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |          for(int i = 0; i<nereikalingi.size(); i++)
      |                         ~^~~~~~~~~~~~~~~~~~~~

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