oj.uz

Submission #1110438

# Submission time Handle Problem Language Result Execution time Memory
1110438 2024-11-09T12:49:21 Z Icelast Palembang Bridges (APIO15_bridge) C++17
100 / 100
 644 ms 29904 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void sub2(int k, int n){
    vector<ll> a(1);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        char s1, s2;
        int l, r;
        cin >> s1 >> l >> s2 >> r;
        if(l > r) swap(l, r);
        if(s1 == s2){
            ans += r-l;
        }else{
            a.push_back(l);
            a.push_back(r);
        }
    }
    sort(a.begin()+1, a.end());
    n = a.size()-1;
    ans += n/2;
    int m = (n+1)/2;
    for(int i = 1; i <= n; i++){
        ans += abs(a[m]-a[i]);
    }
    cout << ans;
    return;
}
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
    ll decode(int x){
        return pot[x-1];
    }
};
// supports: point modify, range apply, range query, walk to find first/last with some precedent
// you are to implement the 2 structs Tag and Info
// for the walks, pass a lambda that takes in Info and return true iff the node with that Info will contain the desired element

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
    int walk(int p, int l, int r, int x, int y, int k) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && info[p].cnt < k) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = walk(2 * p, l, m, x, y, k);
        if (res == -1) {
            res = walk(2 * p + 1, m, r, x, y, k-info[p*2].cnt);
        }
        return res;
    }
    int walk(int l, int r, int k){
        return walk(1, 0, n, l, r, k);
    }
};

struct Tag {
    ll add_cnt = 0, add_sum = 0;
    void apply(const Tag &t) & {
        add_cnt += t.add_cnt;
        add_sum += t.add_sum;
    }
};

struct Info {
    ll cnt = 0, sum = 0;
    void apply(const Tag &t) & {
        cnt += t.add_cnt;
        sum += t.add_sum;
    }
    Info operator+(const Info &b) {
        return {cnt+b.cnt, sum+b.sum};
    }
};
void solve(){
    int k, n;
    cin >> k >> n;
    vector<pair<ll, ll>> a(1);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        char s1, s2;
        int l, r;
        cin >> s1 >> l >> s2 >> r;
        if(l > r) swap(l, r);
        if(s1 == s2){
            ans += r-l;
        }else{
            a.push_back({l, r});
        }
    }
    n = a.size()-1;
    if(n == 0){
        cout << ans;
        return;
    }
    ans += n;
    sort(a.begin()+1, a.end(), [&](pair<ll ,ll> a, pair<ll ,ll> b){return a.first+a.second < b.first+b.second;});
    normalize norm;
    for(int i = 1; i <= n; i++){
        norm.add(a[i].first);
        norm.add(a[i].second);
    }
    norm.start();
    int N = norm.pot.size();
    vector<ll> pf(n+2, 0), sf(n+2, 0);
    auto calc = [&](vector<ll> &pf) -> void{
        LazySegmentTree<Info, Tag> T(N+1);
        for(int i = 1; i <= n; i++){
            int len = i*2, median = (len+1)/2;
            int l = norm.encode(a[i].first), r = norm.encode(a[i].second);
            T.rangeApply(l, l+1, {1, a[i].first});
            T.rangeApply(r, r+1, {1, a[i].second});
            int m = T.walk(1, N+1, median);
            ll valm = norm.decode(m);
            pf[i] = valm*T.rangeQuery(1, m+1).cnt-T.rangeQuery(1, m+1).sum + T.rangeQuery(m+1, N+1).sum-valm*(len-T.rangeQuery(1, m+1).cnt);
        }
    };
    calc(pf);
    a.push_back({0, 0});
    reverse(a.begin(), a.end());
    calc(sf);
    if(k == 1){
        cout << ans+pf[n];
        return;
    }
    ll res = INF;
    for(int i = 0; i <= n; i++){
        res = min(res, pf[i]+sf[n-i]);
    }
    ans += res;
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory 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 4 ms 592 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 3 ms 592 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory 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 5 ms 592 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 4 ms 592 KB Output is correct
12 Correct 37 ms 6400 KB Output is correct
13 Correct 635 ms 27716 KB Output is correct
14 Correct 291 ms 7244 KB Output is correct
15 Correct 335 ms 14216 KB Output is correct
16 Correct 53 ms 6600 KB Output is correct
17 Correct 591 ms 27772 KB Output is correct
18 Correct 583 ms 27592 KB Output is correct
19 Correct 517 ms 27592 KB Output is correct
20 Correct 51 ms 6600 KB Output is correct
21 Correct 499 ms 27672 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory 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 504 KB Output is correct
10 Correct 1 ms 504 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 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 3 ms 592 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 508 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 4 ms 592 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 3 ms 592 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 4 ms 692 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory 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 504 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 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 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 3 ms 592 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 3 ms 592 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 3 ms 592 KB Output is correct
25 Correct 39 ms 6600 KB Output is correct
26 Correct 148 ms 6660 KB Output is correct
27 Correct 581 ms 27392 KB Output is correct
28 Correct 644 ms 27732 KB Output is correct
29 Correct 641 ms 29896 KB Output is correct
30 Correct 301 ms 14868 KB Output is correct
31 Correct 47 ms 8148 KB Output is correct
32 Correct 494 ms 29904 KB Output is correct
33 Correct 547 ms 29668 KB Output is correct
34 Correct 498 ms 29900 KB Output is correct
35 Correct 52 ms 8392 KB Output is correct
36 Correct 544 ms 29820 KB Output is correct
37 Correct 56 ms 7368 KB Output is correct