oj.uz

Submission #1094788

# Submission time Handle Problem Language Result Execution time Memory
1094788 2024-09-30T14:57:44 Z DaciejMaciej Palembang Bridges (APIO15_bridge) C++17
100 / 100
 482 ms 8720 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;

template <class T>

using VV = vector<vector<T>>;

using VI = vector<int>;
using VVI = vector<vector<int>>;

using VL = vector<long long>;
using VVL = vector<vector<long long>>;

using VC = vector<char>;
using VVC = vector<vector<char>>;

using VB = vector<bool>;
using VVB = vector<vector<bool>>;

using VD = vector<double>;
using VVD = vector<vector<double>>;

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using PIL = pair<int, long long>;
using PLI = pair<long long, int>;

using VPII = vector<pair<int, int>>;
using VPLL = vector<pair<long long, long long>>;



#define LINE '\n'
#define SPACE ' '
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i < (int(b)); i++)
#define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sq(a) ((a) * (a))
#define sz(x) ((int)x.size())

#define debug(x) cerr << #x << " = " << x << endl;


// zero indexed
template <class T>
struct segtree
{
    const T def = 0;
    int n;
    vector<T> seg;

    segtree(int _size) : n(_size), seg(2 * _size, def) {}

    T merge(T a, T b)
    {
        return max(a, b);
    }
    void update(int pos, T val)
    {
        for (seg[pos += n] = val; pos /= 2;)
        {
            seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
        }
    }
    T query(int l, int r)
    { // get [l, r]
        T a = def, b = def;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
        {
            if (l % 2)
                a = merge(a, seg[l++]);
            if (r % 2)
                b = merge(b, seg[--r]);
        }
        return merge(a, b);
    }
};

template <class T>
struct BIT
{
    int size;
    vector<T> bit;
    vector<T> arr;

    BIT(int _size) : size(_size), bit(_size + 1), arr(_size) {}

    void set(int pos, T val)
    {
        add(pos, val - arr[pos]);
    }
    void add(int pos, T val)
    {
        arr[pos] += val;

        for (pos++; pos <= size; pos += pos & -pos)
        {
            bit[pos] += val;
        }
    }
    T query(int pos)
    {
        T res = 0;
        for (pos++; pos > 0; pos -= pos & -pos)
        {
            res += bit[pos];
        }
        return res;
    }
};

const ll MOD = 1e9 + 7;

template <class T>
void maxi(T &a, T b)
{
    a = max(a, b);
}

template <class T>
void mini(T &a, T b)
{
    a = min(a, b);
}

template <class T>
void addi(T &a, T b)
{
    a = (a + b) % MOD;
}

template <class T>
void subi(T &a, T b)
{
    a = (a - b + MOD) % MOD;
}

template <class T>
T add(T a, T b)
{
    return (a + b) % MOD;
}

template <class T>
T sub(T a, T b)
{
    return (a - b + MOD) % MOD;
}

template <class T>
T mul(T a, T b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}

ll binpow(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

const int INF = 1e9;

const int MAX_N = 1e5 + 3;


priority_queue<int> lq;
priority_queue<int, VI, greater<int>>  rq;
ll lsum, rsum;

void insert(int x)
{
    int median = (sz(lq) ? lq.top() : 1e9 + 2137);
    if(x <= median) {
        lq.push(x);
        lsum += x;
    }
    else {
        rq.push(x);
        rsum += x;
    }

    if(sz(lq) > sz(rq) + 1) {
        int tmp = lq.top();
        lq.pop();
        rq.push(tmp);
        lsum -= tmp;
        rsum += tmp;
    }
    else if(sz(lq) < sz(rq)) {
        int tmp = rq.top();
        rq.pop();
        lq.push(tmp);
        rsum -= tmp;
        lsum += tmp;
    }
}

void solve()
{
    int n, k;
    cin >> k >> n;

    ll same = 0;

    VPII vec;
    vec.PB({0, 0});

    FOR(i, 0, n) {
        char a, b;
        int x, y;
        cin >> a >> x >> b >> y;
        if(a==b) same += abs(x-y);
        else vec.PB({x, y});
    }

    sort(ALL(vec), [](const PII &a, const PII &b) {return a.first + a.second < b.first + b.second;});
    n = sz(vec) - 1;
    lsum = rsum = 0;
    same += n; // because of bridge

    VL pref(n + 1, 0);

    FOR(i, 1, n + 1) {

        auto [x, y] = vec[i];
        insert(x);
        insert(y);
        cerr << lsum << SPACE << rsum << LINE;
        pref[i] = rsum - lsum;
    }

    ll ans = pref[n];

    if(k == 2) {
        while(sz(lq)) lq.pop();
        while(sz(rq)) rq.pop();

        lsum = rsum = 0;
        for(int i = n; i >= 1; i--) {
            auto [x, y] = vec[i];
            insert(x);
            insert(y);
            mini(ans, rsum - lsum + pref[i-1]);
        }
    }

    cout << same + ans << LINE;
}

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

    int t = 1;
    // cin >> t;

    while (t--)
        solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 5 ms 520 KB Output is correct
8 Correct 5 ms 360 KB Output is correct
9 Correct 5 ms 360 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 4 ms 532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 5 ms 472 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 5 ms 352 KB Output is correct
7 Correct 4 ms 352 KB Output is correct
8 Correct 5 ms 352 KB Output is correct
9 Correct 5 ms 496 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 419 ms 4552 KB Output is correct
13 Correct 449 ms 8448 KB Output is correct
14 Correct 403 ms 6352 KB Output is correct
15 Correct 268 ms 5272 KB Output is correct
16 Correct 428 ms 6604 KB Output is correct
17 Correct 474 ms 8400 KB Output is correct
18 Correct 428 ms 8000 KB Output is correct
19 Correct 444 ms 8352 KB Output is correct
20 Correct 425 ms 7112 KB Output is correct
21 Correct 448 ms 7732 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 1 ms 472 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 5 ms 508 KB Output is correct
20 Correct 5 ms 348 KB Output is correct
21 Correct 6 ms 348 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 5 ms 472 KB Output is correct
24 Correct 5 ms 348 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 3 ms 352 KB Output is correct
18 Correct 2 ms 352 KB Output is correct
19 Correct 4 ms 352 KB Output is correct
20 Correct 5 ms 352 KB Output is correct
21 Correct 5 ms 352 KB Output is correct
22 Correct 5 ms 348 KB Output is correct
23 Correct 5 ms 348 KB Output is correct
24 Correct 5 ms 360 KB Output is correct
25 Correct 431 ms 4668 KB Output is correct
26 Correct 447 ms 6108 KB Output is correct
27 Correct 482 ms 7368 KB Output is correct
28 Correct 479 ms 8720 KB Output is correct
29 Correct 474 ms 8588 KB Output is correct
30 Correct 257 ms 4564 KB Output is correct
31 Correct 426 ms 6604 KB Output is correct
32 Correct 463 ms 8400 KB Output is correct
33 Correct 473 ms 7680 KB Output is correct
34 Correct 465 ms 8400 KB Output is correct
35 Correct 445 ms 7092 KB Output is correct
36 Correct 450 ms 7628 KB Output is correct
37 Correct 429 ms 4316 KB Output is correct