oj.uz

답안 #1101094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1101094 2024-10-15T13:28:23 Z Zero_OP Palembang Bridges (APIO15_bridge) C++17
100 / 100
 66 ms 6344 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

void testcase(){
    int k, n;
    cin >> k >> n;
    vector<pair<int, int>> opposite;
    vector<int> values;

    ll answer = 0;
    rep(i, 0, n){
        char b1, b2;
        int x1, x2;

        cin >> b1 >> x1 >> b2 >> x2;

        if(b1 == b2) answer += abs(x1 - x2);
        else {
            opposite.push_back({x1, x2});
            values.push_back(x1);
            values.push_back(x2);
        }
    }

    n = sz(opposite);
    answer += n;

    if(k == 1){
        if(!values.empty()){
            sort(all(values));
            int median = values[sz(values) / 2];
            for(int i = 0; i < n; ++i){
                answer += abs(opposite[i].first - median) + abs(opposite[i].second - median);
            }
        }
    } else{
        if(!opposite.empty()){
            sort(all(opposite), [&](const pair<int, int>& p1, const pair<int, int>& p2){
                return p1.first + p1.second < p2.first + p2.second;
            });

            priority_queue<int> left;
            priority_queue<int, vector<int>, greater<int>> right;

            vector<ll> pref(n);
            ll left_sum = 0, right_sum = 0, cur = 0;
            int median = -1;

            auto add = [&](int x) -> void{
                left.push(x);
                left_sum += x;

                while(sz(left) > sz(right)){
                    int y = left.top();
                    left_sum -= y;
                    left.pop();
                    right.push(y);
                    right_sum += y;
                }

                while(!left.empty() && !right.empty() && left.top() > right.top()){
                    int u = left.top();
                    int v = right.top();

                    left_sum -= u;
                    right_sum -= v;

                    left.pop();
                    right.pop();

                    left.push(v);
                    right.push(u);

                    left_sum += v;
                    right_sum += u;
                }

                median = right.top();
            };

            for(int i = 0; i < n; ++i){
                add(opposite[i].first);
                add(opposite[i].second);

                cur = 1ll * sz(left) * median - left_sum + right_sum - 1ll * sz(right) * median;
                pref[i] = cur;
            }

            priority_queue<int>().swap(left);
            priority_queue<int, vector<int>, greater<int>>().swap(right);
            left_sum = 0;
            right_sum = 0;
            cur = 0;

            ll extra = pref[n - 1];

            for(int i = n - 1; i >= 0; --i){
                add(opposite[i].first);
                add(opposite[i].second);

                cur = 1ll * sz(left) * median - left_sum + right_sum - 1ll * sz(right) * median;
                minimize(extra, cur + (i > 0 ? pref[i - 1] : 0));
            }

            answer += extra;
        }
    }

    cout << answer << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int T = 1; //cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message

bridge.cpp: In function 'bool minimize(T&, const T&)':
bridge.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
bridge.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
bridge.cpp: In function 'bool maximize(T&, const T&)':
bridge.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
bridge.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 16 ms 3004 KB Output is correct
13 Correct 34 ms 4308 KB Output is correct
14 Correct 22 ms 3268 KB Output is correct
15 Correct 18 ms 2756 KB Output is correct
16 Correct 19 ms 3668 KB Output is correct
17 Correct 21 ms 2248 KB Output is correct
18 Correct 26 ms 4028 KB Output is correct
19 Correct 30 ms 4468 KB Output is correct
20 Correct 20 ms 4196 KB Output is correct
21 Correct 33 ms 2236 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 1 ms 472 KB Output is correct
24 Correct 1 ms 336 KB Output is correct

Subtask #5
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 496 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 352 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 34 ms 4000 KB Output is correct
26 Correct 53 ms 4960 KB Output is correct
27 Correct 61 ms 4032 KB Output is correct
28 Correct 64 ms 6344 KB Output is correct
29 Correct 66 ms 6292 KB Output is correct
30 Correct 35 ms 3620 KB Output is correct
31 Correct 37 ms 5664 KB Output is correct
32 Correct 50 ms 6336 KB Output is correct
33 Correct 51 ms 4072 KB Output is correct
34 Correct 58 ms 6336 KB Output is correct
35 Correct 46 ms 5936 KB Output is correct
36 Correct 53 ms 6040 KB Output is correct
37 Correct 23 ms 4796 KB Output is correct