Submission #593283

#	Time	Username	Problem	Language	Result	Execution time	Memory
593283		AlperenT	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	312 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

const int N = 1e5 + 5;

struct SegTree{
    long long tree[N * 4], lazy[N * 4];

    void push(int v){
        if(lazy[v]){
            tree[v] += lazy[v];

            if(v * 2 < N * 4) lazy[v * 2] += lazy[v], tree[v * 2 + 1] += lazy[v];

            lazy[v] = 0;
        }
    }

    long long merge(long long a, long long b){
        return min(a, b);
    }

    void build(int v, int l, int r, vector<long long> &arr){
        lazy[v] = tree[v] = 0;

        if(l == r) tree[v] = arr[l];
        else{
            int m = l + (r - l) / 2;

            build(v * 2, l, m, arr);
            build(v * 2 + 1, m + 1, r, arr);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    void update(int v, int tl, int tr, int l, int r, long long val){
        if(l > r) return;
        else if(tl == l && tr == r) lazy[v] += val;
        else{
            push(v);

            int tm = tl + (tr - tl) / 2;

            update(v * 2, tl, tm, l, min(tm, r), val);
            update(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, val);

            push(v * 2), push(v * 2 + 1);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    long long query(){
        push(1);

        return tree[1];
    }
};

SegTree sgt;

struct Item{
    vector<int> pos;

    vector<long long> prefix, suffix, dp;
};

long long min_total_length(vector<int> r, vector<int> b){
    vector<pair<int, bool>> v;

    for(auto x : r) v.push_back({x, false});
    for(auto x : b) v.push_back({x, true});

    sort(v.begin(), v.end());

    vector<Item> vec;

    vec.push_back({{v.front().first}, {}, {}, {}});

    for(int i = 1; i < v.size(); i++){
        if(v[i].second == v[i - 1].second) vec.back().pos.push_back(v[i].first);
        else vec.push_back({{v[i].first}, {}, {}, {}});
    }

    for(auto &itm : vec){
        itm.prefix.assign(itm.pos.size(), 0);
        itm.suffix.assign(itm.pos.size(), 0);
        itm.dp.assign(itm.pos.size() + 1, 0);

        for(int i = 1; i < itm.pos.size(); i++) itm.prefix[i] = itm.prefix[i - 1] + (itm.pos[i] - itm.pos.front());
        for(int i = (int)itm.pos.size() - 2; i >= 0; i--) itm.suffix[i] = itm.suffix[i + 1] + (itm.pos.back() - itm.pos[i]);
    }

    for(int cur = 1; cur < vec.size(); cur++){
        vector<long long> prvdp = vec[cur - 1].dp;

        for(int i = 0; i < vec[cur - 1].pos.size(); i++) prvdp[i] += vec[cur - 1].suffix[i] + 1ll * (vec[cur - 1].pos.size() - i) * (vec[cur].pos.front() - vec[cur - 1].pos.back());

        sgt.build(1, 0, prvdp.size() - 1, prvdp);

        vec[cur].dp[0] = sgt.query();

        for(int i = 1; i < vec[cur].dp.size(); i++){
            sgt.update(1, 0, prvdp.size() - 1, max((int)prvdp.size() - i, 0), prvdp.size() - 1, vec[cur].pos.front() - vec[cur - 1].pos.back());

            vec[cur].dp[i] = sgt.query() + vec[cur].prefix[i - 1];
        }
    }

    return vec.back().dp.back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 1; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
wiring.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int i = 1; i < itm.pos.size(); i++) itm.prefix[i] = itm.prefix[i - 1] + (itm.pos[i] - itm.pos.front());
      |                        ~~^~~~~~~~~~~~~~~~
wiring.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int cur = 1; cur < vec.size(); cur++){
      |                      ~~~~^~~~~~~~~~~~
wiring.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i = 0; i < vec[cur - 1].pos.size(); i++) prvdp[i] += vec[cur - 1].suffix[i] + 1ll * (vec[cur - 1].pos.size() - i) * (vec[cur].pos.front() - vec[cur - 1].pos.back());
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i = 1; i < vec[cur].dp.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45