oj.uz

Submission #282872

# Submission time Handle Problem Language Result Execution time Memory
282872 2020-08-25T05:59:34 Z IgorI Palembang Bridges (APIO15_bridge) C++17
100 / 100
 542 ms 23928 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll ans0, ans;

vector<pair<int, int> > a;

bool comp(pair<int, int> x, pair<int, int> y)
{
    return x.first + x.second < y.first + y.second;
}

struct MedianGetter{
    set<pair<int, int> > s0, s1;
    int tot = 0;
    ll si0 = 0, si1 = 0;
    void add(int x)
    {
        pair<int, int> elem = {x, tot};
        tot++;
        if (s0.size() == 0)
        {
            s0.insert(elem);
            si0 += x;
            return;
        }
        auto it = s0.end();
        it--;
        if (x <= (*it).first)
        {
            s0.insert(elem);
            si0 += x;
        }
        else
        {
            s1.insert(elem);
            si1 += x;
        }
        while (s0.size() < (tot + 1) / 2)
        {
            pair<int, int> z = *(s1.begin());
            s1.erase(s1.begin());
            si1 -= z.first;
            si0 += z.first;
            s0.insert(z);
        }
        while (s0.size() > (tot + 1) / 2)
        {
            auto it = s0.end();
            it--;
            pair<int, int> z = *(it);
            s0.erase(it);
            si0 -= z.first;
            si1 += z.first;
            s1.insert(z);
        }
    }
    int get()
    {
        auto it = s0.end();
        it--;
        return (*it).first;
    }
};

signed main()
{
    int n, k;
    cin >> k >> n;
    for (int i = 0; i < n; i++)
    {
        string c, d;
        int x, y;
        cin >> c >> x >> d >> y;
        if (c == d) ans0 += abs(x - y);
        else a.push_back({x, y});
    }
    if (a.size() == 0)
    {
        cout << ans0;
        return 0;
    }
    sort(a.begin(), a.end(), comp);
    vector<ll> optpref(a.size()), optsuff(a.size());
    MedianGetter M1;
    for (int i = 0; i < a.size(); i++)
    {
        M1.add(a[i].first);
        M1.add(a[i].second);
        optpref[i] = M1.si1 - M1.si0;
    }
    MedianGetter M2;
    for (int i = (int)a.size() - 1; i >= 0; i--)
    {
        M2.add(a[i].first);
        M2.add(a[i].second);
        optsuff[i] = M2.si1 - M2.si0;
    }
    if (k == 1)
    {
        cout << ans0 + optpref[a.size() - 1] + a.size();
        return 0;
    }
    //for (int i = 0; i < n; i++) cout << optpref[i] << " "; cout << "\n";
    //for (int i = 0; i < n; i++) cout << optsuff[i] << " "; cout << "\n";
    ans = min(optpref[a.size() - 1], optsuff[0]);
    for (int i = 0; i + 1 < a.size(); i++) ans = min(ans, optpref[i] + optsuff[i + 1]);
    cout << ans0 + ans + a.size();
}

Compilation message

bridge.cpp: In member function 'void MedianGetter::add(int)':
bridge.cpp:42:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         while (s0.size() < (tot + 1) / 2)
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~
bridge.cpp:50:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         while (s0.size() > (tot + 1) / 2)
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
bridge.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i + 1 < a.size(); i++) ans = min(ans, optpref[i] + optsuff[i + 1]);
      |                     ~~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 246 ms 22376 KB Output is correct
13 Correct 517 ms 23796 KB Output is correct
14 Correct 376 ms 20536 KB Output is correct
15 Correct 261 ms 14192 KB Output is correct
16 Correct 304 ms 23312 KB Output is correct
17 Correct 349 ms 23928 KB Output is correct
18 Correct 295 ms 23548 KB Output is correct
19 Correct 357 ms 23920 KB Output is correct
20 Correct 321 ms 23400 KB Output is correct
21 Correct 351 ms 23660 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 4 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 4 ms 512 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 263 ms 22248 KB Output is correct
26 Correct 337 ms 22508 KB Output is correct
27 Correct 477 ms 23144 KB Output is correct
28 Correct 542 ms 23912 KB Output is correct
29 Correct 504 ms 23788 KB Output is correct
30 Correct 223 ms 12784 KB Output is correct
31 Correct 304 ms 23148 KB Output is correct
32 Correct 347 ms 23928 KB Output is correct
33 Correct 293 ms 23516 KB Output is correct
34 Correct 349 ms 23920 KB Output is correct
35 Correct 323 ms 23408 KB Output is correct
36 Correct 361 ms 23660 KB Output is correct
37 Correct 239 ms 22376 KB Output is correct