oj.uz

Submission #922913

# Submission time Handle Problem Language Result Execution time Memory
922913 2024-02-06T09:15:35 Z vjudge1 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 120 ms 24272 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 3e5 + 7;

int n, k;

vector<pii> seg;

ll res = 0;

namespace sub1 {
    ll pre[N], suf[N];
    ll pre_cnt[N], suf_cnt[N];
    vector<int> E;
    int idx(int x) {
        return lower_bound(all(E), x) - E.begin() + 1;
    }
    void buildE() {
        set<int> s;
        for (auto x : seg) {
            s.insert(x.X);
            s.insert(x.Y);
        }
        E = vector<int>(s.begin(), s.end());
    }
    void Process() {
        buildE();
        int m = (int)E.size();
        ll ANS = 9e18;
        pre[0] = suf[n + 1] = 0;
        pre_cnt[0] = suf_cnt[n + 1] = 0;
        for (auto x : seg) {
            pre[idx(x.Y)]+=x.Y;
            pre_cnt[idx(x.Y)]++;
            suf[idx(x.X)]+=x.X;
            suf_cnt[idx(x.X)]++;
        }
        FOR(i, 1, m) {
            pre[i]+=pre[i - 1];
            pre_cnt[i]+=pre_cnt[i - 1];
        }
        FORD(i, m, 1) {
            suf[i]+=suf[i + 1];
            suf_cnt[i]+=suf_cnt[i + 1];
        }
        FOR(i, 1, m) {
            int x = E[i - 1];
            ll ans = 2LL * (pre_cnt[i - 1] * x - pre[i - 1]);
            ans+=2LL * (suf[i + 1] - suf_cnt[i + 1] * x);
            minimize(ANS, res + ans);
        }
        cout<<ANS;
    }
}

namespace sub2 {
    ll pre[N], suf[N];
    vector<int> E;
    int idx(int x) {
        return lower_bound(all(E), x) - E.begin() + 1;
    }
    void buildE() {
        set<int> s;
        for (auto x : seg) {
            s.insert(x.X);
            s.insert(x.Y);
        }
        E = vector<int>(s.begin(), s.end());
    }
    ll pre_res[N], suf_res[N];
    ll tmp[N];
    void Process() {
        buildE();
        int m = (int)E.size();
        ll ANS = 9e18;
        sort(all(seg));
        set<int> point;
        for (auto x : seg) {
            point.insert(x.X);
            point.insert(x.Y);
        }
        FOR(i, 0, (int)point.size()) pre_res[i] = suf_res[i] = 1e18;
        for (auto x : point) {
            ll cost = 0;
            REP(i, 0, (int)seg.size()) {
                if (seg[i].Y < x) cost+=2LL * (x - seg[i].Y); else
                if (seg[i].X > x) cost+=2LL * (seg[i].X - x);
                minimize(pre_res[i], cost);
            }
            cost = 0;
            FORD(i, (int)seg.size() - 1, 0) {
                if (seg[i].Y < x) cost+=2LL * (x - seg[i].Y); else
                if (seg[i].X > x) cost+=2LL * (seg[i].X - x);
                minimize(suf_res[i], cost);
            }
        }
        minimize(ANS, suf_res[0] + res);
        minimize(ANS, pre_res[(int)point.size() - 1] + res);
        REP(i, 0, (int)point.size() - 1) minimize(ANS, pre_res[i] + suf_res[i + 1] + res);
        cout<<ANS;
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>k>>n;
    FOR(i, 1, n) {
        char P, Q;
        int A, B;
        cin>>P>>A>>Q>>B;
        res+=abs(A - B);
        if (P != Q) seg.push_back({min(A, B), max(A, B)}), res++;
    }
    if (seg.empty()) return cout<<res, 0;
    if (k == 1) {
        sub1::Process();
        return 0;
    }
    if (k == 2) {
        sub2::Process();
        return 0;
    }
    return 0;
}

Compilation message

bridge.cpp: In function 'void sub2::Process()':
bridge.cpp:113:13: warning: unused variable 'm' [-Wunused-variable]
  113 |         int m = (int)E.size();
      |             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10636 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4544 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 11096 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 16 ms 13548 KB Output is correct
13 Correct 120 ms 24272 KB Output is correct
14 Correct 60 ms 14084 KB Output is correct
15 Correct 66 ms 19588 KB Output is correct
16 Correct 20 ms 13772 KB Output is correct
17 Correct 76 ms 23940 KB Output is correct
18 Correct 84 ms 23812 KB Output is correct
19 Correct 97 ms 23756 KB Output is correct
20 Correct 23 ms 13776 KB Output is correct
21 Correct 73 ms 24212 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 1 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Incorrect 2 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 1 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -