oj.uz

답안 #1110407

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1110407 2024-11-09T11:36:55 Z Icelast Palembang Bridges (APIO15_bridge) C++17
22 / 100
 36 ms 3700 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;});
    return;
    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 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 2 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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 504 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 2 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 15 ms 3700 KB Output is correct
13 Correct 36 ms 3532 KB Output is correct
14 Correct 25 ms 2656 KB Output is correct
15 Correct 29 ms 1488 KB Output is correct
16 Correct 19 ms 2508 KB Output is correct
17 Correct 22 ms 3624 KB Output is correct
18 Correct 25 ms 3532 KB Output is correct
19 Correct 30 ms 2508 KB Output is correct
20 Correct 20 ms 2508 KB Output is correct
21 Correct 28 ms 2508 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -