oj.uz

답안 #1110406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1110406 2024-11-09T11:36:31 Z Icelast Palembang Bridges (APIO15_bridge) C++17
22 / 100
 40 ms 5084 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<int, int>> 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<int ,int> a, pair<int ,int> 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 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++){
      |                        ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 648 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 472 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 16 ms 3296 KB Output is correct
13 Correct 35 ms 4300 KB Output is correct
14 Correct 24 ms 3788 KB Output is correct
15 Correct 28 ms 2764 KB Output is correct
16 Correct 20 ms 4868 KB Output is correct
17 Correct 40 ms 5084 KB Output is correct
18 Correct 27 ms 4044 KB Output is correct
19 Correct 34 ms 4300 KB Output is correct
20 Correct 28 ms 2584 KB Output is correct
21 Correct 28 ms 5068 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -