oj.uz

Submission #1117208

# Submission time Handle Problem Language Result Execution time Memory
1117208 2024-11-23T01:11:49 Z ShaShi Palembang Bridges (APIO15_bridge) C++17
100 / 100
 91 ms 57016 KB 
#include <bits/stdc++.h>
 
#define int long long 
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e18 + 7;
 
 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, res, pre_ans;
char ch, ch2;
vector<int> vec[2][MAXN], cmp;
vector<pair<int, pii>> ord;
int ps[2][MAXN];


/* Median DS */
priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<int>> rpq;
int lsum, rsum;


inline void add(int x) {
    int median = (lpq.size()? lpq.top() : INF);

    if (x <= median) lpq.push(x), lsum += x;
    else rpq.push(x), rsum += x;

    if (lpq.size() < rpq.size()) {
        rsum -= rpq.top(); lsum += rpq.top();
        lpq.push(rpq.top()); rpq.pop();
    } else if (rpq.size()+1 < lpq.size()) {
        lsum -= lpq.top(); rsum += lpq.top();
        rpq.push(lpq.top()); lpq.pop();
    }
}

/* Median DS */
 

int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif
 
    cin >> k >> n;
 
    for (int i=1; i<=n; i++) {
        cin >> ch >> u >> ch2 >> v;
 
        if (ch == ch2) pre_ans += abs(u-v);
        else ord.pb({u+v, {u, v}});
    }

    N = ord.size(); sort(all(ord)); pre_ans += N;

    lsum = rsum = 0;

    for (int i=1; i<=N; i++) {
        add(ord[i-1].S.F); add(ord[i-1].S.S);

        ps[0][i] = rsum - lsum;
    }

    ans = ps[0][N];

    if (k == 1) kill(ans+pre_ans);

    lsum = rsum = 0;
    while (lpq.size()) lpq.pop();
    while (rpq.size()) rpq.pop();

    for (int i=N; i>=1; i--) {
        add(ord[i-1].S.F); add(ord[i-1].S.S);

        ans = min(ans, rsum - lsum + ps[0][i-1]);
    }

    cout << pre_ans+ans << endl;

    
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 48464 KB Output is correct
2 Correct 13 ms 48344 KB Output is correct
3 Correct 18 ms 48464 KB Output is correct
4 Correct 18 ms 48440 KB Output is correct
5 Correct 15 ms 48464 KB Output is correct
6 Correct 18 ms 48464 KB Output is correct
7 Correct 22 ms 48464 KB Output is correct
8 Correct 20 ms 48464 KB Output is correct
9 Correct 22 ms 48464 KB Output is correct
10 Correct 23 ms 48600 KB Output is correct
11 Correct 20 ms 48476 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48464 KB Output is correct
2 Correct 15 ms 48352 KB Output is correct
3 Correct 14 ms 48464 KB Output is correct
4 Correct 16 ms 48564 KB Output is correct
5 Correct 15 ms 48404 KB Output is correct
6 Correct 18 ms 48464 KB Output is correct
7 Correct 19 ms 48476 KB Output is correct
8 Correct 14 ms 48464 KB Output is correct
9 Correct 14 ms 48464 KB Output is correct
10 Correct 18 ms 48464 KB Output is correct
11 Correct 17 ms 48464 KB Output is correct
12 Correct 39 ms 55232 KB Output is correct
13 Correct 60 ms 56556 KB Output is correct
14 Correct 64 ms 55504 KB Output is correct
15 Correct 45 ms 53444 KB Output is correct
16 Correct 47 ms 56256 KB Output is correct
17 Correct 52 ms 56760 KB Output is correct
18 Correct 56 ms 56556 KB Output is correct
19 Correct 54 ms 56768 KB Output is correct
20 Correct 50 ms 56496 KB Output is correct
21 Correct 61 ms 56504 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48464 KB Output is correct
2 Correct 29 ms 48460 KB Output is correct
3 Correct 28 ms 48456 KB Output is correct
4 Correct 30 ms 48464 KB Output is correct
5 Correct 26 ms 48464 KB Output is correct
6 Correct 20 ms 48464 KB Output is correct
7 Correct 23 ms 48440 KB Output is correct
8 Correct 25 ms 48464 KB Output is correct
9 Correct 24 ms 48376 KB Output is correct
10 Correct 20 ms 48464 KB Output is correct
11 Correct 24 ms 48464 KB Output is correct
12 Correct 25 ms 48464 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 48464 KB Output is correct
2 Correct 24 ms 48464 KB Output is correct
3 Correct 29 ms 48464 KB Output is correct
4 Correct 24 ms 48464 KB Output is correct
5 Correct 24 ms 48536 KB Output is correct
6 Correct 21 ms 48552 KB Output is correct
7 Correct 20 ms 48464 KB Output is correct
8 Correct 18 ms 48436 KB Output is correct
9 Correct 20 ms 48540 KB Output is correct
10 Correct 18 ms 48464 KB Output is correct
11 Correct 17 ms 48464 KB Output is correct
12 Correct 18 ms 48464 KB Output is correct
13 Correct 20 ms 48464 KB Output is correct
14 Correct 21 ms 48464 KB Output is correct
15 Correct 24 ms 48384 KB Output is correct
16 Correct 22 ms 48464 KB Output is correct
17 Correct 24 ms 48464 KB Output is correct
18 Correct 21 ms 48456 KB Output is correct
19 Correct 23 ms 48464 KB Output is correct
20 Correct 27 ms 48408 KB Output is correct
21 Correct 23 ms 48464 KB Output is correct
22 Correct 21 ms 48464 KB Output is correct
23 Correct 26 ms 48476 KB Output is correct
24 Correct 24 ms 48464 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48464 KB Output is correct
2 Correct 25 ms 48464 KB Output is correct
3 Correct 24 ms 48480 KB Output is correct
4 Correct 26 ms 48464 KB Output is correct
5 Correct 24 ms 48464 KB Output is correct
6 Correct 25 ms 48464 KB Output is correct
7 Correct 23 ms 48476 KB Output is correct
8 Correct 28 ms 48420 KB Output is correct
9 Correct 23 ms 48464 KB Output is correct
10 Correct 23 ms 48464 KB Output is correct
11 Correct 29 ms 48464 KB Output is correct
12 Correct 25 ms 48464 KB Output is correct
13 Correct 23 ms 48464 KB Output is correct
14 Correct 22 ms 48720 KB Output is correct
15 Correct 19 ms 48464 KB Output is correct
16 Correct 17 ms 48540 KB Output is correct
17 Correct 18 ms 48464 KB Output is correct
18 Correct 19 ms 48464 KB Output is correct
19 Correct 24 ms 48632 KB Output is correct
20 Correct 20 ms 48420 KB Output is correct
21 Correct 20 ms 48464 KB Output is correct
22 Correct 20 ms 48464 KB Output is correct
23 Correct 23 ms 48464 KB Output is correct
24 Correct 20 ms 48464 KB Output is correct
25 Correct 51 ms 55216 KB Output is correct
26 Correct 76 ms 55736 KB Output is correct
27 Correct 91 ms 56228 KB Output is correct
28 Correct 91 ms 57016 KB Output is correct
29 Correct 86 ms 56512 KB Output is correct
30 Correct 54 ms 52668 KB Output is correct
31 Correct 56 ms 56276 KB Output is correct
32 Correct 71 ms 56760 KB Output is correct
33 Correct 82 ms 56388 KB Output is correct
34 Correct 83 ms 56900 KB Output is correct
35 Correct 60 ms 56460 KB Output is correct
36 Correct 77 ms 56516 KB Output is correct
37 Correct 46 ms 55224 KB Output is correct