oj.uz

Submission #1110409

# Submission time Handle Problem Language Result Execution time Memory
1110409 2024-11-09T11:38:46 Z Icelast Palembang Bridges (APIO15_bridge) C++17
22 / 100
 30 ms 3532 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, decode;
    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]);
            }
        }
        decode.clear();
        decode.resize(pot.size()+1);
        for(int i = 1; i <= pot.size(); i++){
            decode[i] = pot[i-1];
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+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);
    }
};

struct Tag {
    int 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;
    if(k == 1){
        sub2(k, n);
        return;
    }
    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;
    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();
    return;
    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 low = 1, high = n, mid;
            while(low <= high){
                mid = (low+high)/2;
                if(T.rangeQuery(1, mid+1).cnt < median){
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }
            int m = low;
            ll valm = norm.decode[m];
            pf[i] = valm*median-T.rangeQuery(1, m+1).sum + T.rangeQuery(m+1, N+1).sum-valm*(len-median);
        }
    };
    return;
    calc(pf);
    a.push_back({0, 0});
    reverse(a.begin(), a.end());
    calc(sf);
    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);
    solve();
}

Compilation message

bridge.cpp: In member function 'void normalize::start()':
bridge.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 1; i <= pot.size(); i++){
      |                        ~~^~~~~~~~~~~~~
bridge.cpp: In lambda function:
bridge.cpp:254:43: warning: narrowing conversion of '(& a)->std::vector<std::pair<long long int, long long int> >::operator[](((std::vector<std::pair<long long int, long long int> >::size_type)i)).std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  254 |             T.rangeApply(l, l+1, {1, a[i].first});
bridge.cpp:255:43: warning: narrowing conversion of '(& a)->std::vector<std::pair<long long int, long long int> >::operator[](((std::vector<std::pair<long long int, long long int> >::size_type)i)).std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  255 |             T.rangeApply(r, r+1, {1, a[i].second});

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 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 504 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

# 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 504 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 15 ms 3532 KB Output is correct
13 Correct 30 ms 3504 KB Output is correct
14 Correct 22 ms 3532 KB Output is correct
15 Correct 19 ms 1488 KB Output is correct
16 Correct 17 ms 3532 KB Output is correct
17 Correct 21 ms 3532 KB Output is correct
18 Correct 23 ms 3532 KB Output is correct
19 Correct 29 ms 3532 KB Output is correct
20 Correct 20 ms 3532 KB Output is correct
21 Correct 27 ms 3532 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -