Submission #1282008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282008		swishy123	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	38 ms	63308 KiB

bridge

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <iomanip>
#include <queue>
#include <cassert>
#include <complex>
#include <cstring>
#include <memory>
#include <bitset>
#include <sstream>
#include <cmath>
#include <numeric>
#include <numbers>
#include <fstream>

using namespace std;

// #include <genlib.h>
// using namespace genlib;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #include <tr2/dynamic_bitset>   
// using namespace tr2;

#ifndef template
#ifndef define

#pragma GCC target("popcnt")
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define pi pair<int, int>
#define nl cout << '\n';
#define x first
#define y second 
#define cbit(x) __builtin_popcountll(x)
#define uid(a, b) uniform_int_distribution<ll>(a, b)(rng) 
#define siz(x) (int)x.size()
#define all(x) (x).begin(), (x).end() 
 
#endif
 
#ifndef print
void print(size_t x) {cout << x << ' ';}
void print(int x) {cout << x << ' ';}
void print(long long x) {cout << x << ' ';}
void print(float x) {cout << x << ' ';}
void print(long double x) {cout << x << ' ';}
void print(char x) {cout << x << ' ';}
void print(const char* x) {cout << x << ' ';}
void print(bool x) {cout << x << ' ';}
void print(string &x) {cout << x << ' ';}
 
template<typename T, typename V>
void print(pair<T, V> &p) {print(p.x); print(p.y);}
template<typename T>
void print(vector<T> v) {for (int i = 0; i < v.size(); i++) print(v[i]);}
template<typename T>
void print(vector<vector<T>> v) {
    for (int i = 0; i < v.size(); i++){
        for (int j = 0; j < v[i].size(); j++)
            print(v[i][j]);
        nl;
    }
}
template <typename T, typename... V>
void print(T t, V&&... v) {print(t); print(v...);}
 
#endif
 
#ifndef read
void read(int &x) {cin >> x;}
void read(long long &x) {cin >> x;}
void read(unsigned &x) {cin >> x;}
void read(unsigned long long &x) {cin >> x;}
void read(float &x) {cin >> x;}
void read(long double &x) {cin >> x;}
void read(char &x) {cin >> x;}
void read(string &x) {cin >> x;}
void read(bool &x) {cin >> x;}
 
template<typename T> 
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++)
        read(v[i]);
}
template <typename T, typename... V>
void read(T &t, V&... v) {read(t); read(v...);}
#endif
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> bool maxi(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template<class T> bool mini(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template<class... Args>
auto vec(size_t n, Args&&... args) {
    if constexpr(sizeof...(args) == 1)
        return vector(n, args...);
    else
        return vector(n, vec(args...));
}
 
#endif

const ll inf = 1e18;
const ll def = 2e6+1;
const ll mod = 1e9+7;

struct Segment{
    int l, r;
    float mid;
    Segment(int l, int r) : l(l), r(r){
        mid = (float)(l + r) / (float)2;
    }
};

struct Node{
    ll sum, lazy, l, r;

    Node(){}
    Node(int l, int r) : lazy(0), sum(0), l(-1), r(-1){} 
};

vector<pi> v2;
Node st[def];

void build(int l, int r, int crr){
    if (l == r){
        st[crr].l = v2[l].x;
        st[crr].r = v2[l].y;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, crr * 2 + 1);
    build(mid + 1, r, crr * 2 + 2);

    st[crr].l = st[crr * 2 + 1].l;
    st[crr].r = st[crr * 2 + 2].r;
}

void push(int l, int r, int crr){
    ll lazy = st[crr].lazy;

    st[crr * 2 + 1].sum += lazy * (st[crr * 2 + 1].r - st[crr * 2 + 1].l + 1);
    st[crr * 2 + 2].sum += lazy * (st[crr * 2 + 2].r - st[crr * 2 + 2].l + 1);

    st[crr * 2 + 1].lazy += lazy;
    st[crr * 2 + 2].lazy += lazy;

    st[crr].lazy = 0;
}

void update(int l, int r, int ql, int qr, int crr, ll x){
    if (l > qr || r < ql)
        return;
    if (l >= ql && r <= qr){
        st[crr].lazy += x;
        st[crr].sum += x * (st[crr].r - st[crr].l + 1);
        return;
    }
    push(l, r, crr);

    int mid = (l + r) / 2;
    update(l, mid, ql, qr, crr * 2 + 1, x);
    update(mid + 1, r, ql, qr, crr * 2 + 2, x);

    st[crr].sum = st[crr * 2 + 1].sum + st[crr * 2 + 2].sum;
}

ll get(int l, int r, int ql, int qr, int crr){
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return st[crr].sum;
    push(l, r, crr);

    int mid = (l + r) / 2;
    return get(l, mid, ql, qr, crr * 2 + 1) + get(mid + 1, r, ql, qr, crr * 2 + 2);
}

void solve(){
    int k, n;
    cin >> k >> n;

    ll add = 0;
    vector<Segment> sm;

    vector<int> v;
    for (int i = 0; i < n; i++){
        char p, q;
        ll s, t;

        read(p, s, q, t);
        if (p == q)
            add += abs(s - t);
        else{
            add++;
            if (s > t)
                swap(s, t);
            v.push_back(s);
            v.push_back(t);
            sm.push_back(Segment(s, t));
        }
    }

    v.push_back(0);
    v.push_back(1e9);

    sort(v.begin(), v.end());
    v.erase(unique(all(v)), v.end());

    for (int i = 0; i < v.size(); i++){
        v2.push_back({v[i], v[i]});
        if (i + 1 < v.size()){
            if (v[i] + 1 <= v[i + 1] - 1)
            v2.push_back({v[i] + 1, v[i + 1] - 1});
        }
    }
    map<int, int> mp;
    for (int i = 0; i < v2.size(); i++)
        mp[v2[i].x] = i;

    int m = v2.size();
    build(0, m - 1, 0);

    n = sm.size();
    sort(sm.begin(), sm.end(), [](Segment a, Segment b){
        return a.mid < b.mid;
    });

    int bound = 1e9;

    vector<ll> pref(n + 1, inf);
    vector<ll> suff(n + 1, inf);
    
    pref[0] = 0;
    suff[0] = 0;
    
    for (int o = 0; o < 2; o++){
        for (int i = 0; i < def; i++)
            st[i].lazy = st[i].sum = 0;
            
        for (int i = 1; i <= n; i++){
            int l = sm[i - 1].l, r = sm[i - 1].r;   
            update(0, m - 1, 0, 0, 0, (r - l) + l * 2 + 2);
            update(0, m - 1, 0, mp[l], 0, -2);
            update(0, m - 1, mp[r + 1], m - 1, 0, 2);

            l = 0, r = v.size() - 1;
            while (r - l > 3){
                int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
                ll val1 = get(0, m - 1, 0, mp[v[mid1]], 0), val2 = get(0, m - 1, 0, mp[v[mid2]], 0);
    
                if (val1 <= val2)
                    r = mid2;
                else
                    l = mid1;
            }
            for (int j = l; j <= r; j++)
                pref[i] = min(pref[i], get(0, m - 1, 0, v[j], 0));
        }
        reverse(sm.begin(), sm.end());
        swap(pref, suff);
    }
    reverse(suff.begin(), suff.end());

    if (k == 1)
        cout << pref[n] + add;
    else{
        ll res = inf;
        for (int i = 0; i <= n; i++)
            res = min(res, pref[i] + suff[i]);
        cout << res + add;
    }
}                 

/* 
*/  

main(){ 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (ifstream("input.txt").good()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    }

    int t;
    t = 1;
    
    while (t--){
        solve();
        nl;
    }
}

Compilation message (stderr)

bridge.cpp:295:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  295 | main(){
      | ^~~~
bridge.cpp: In function 'int main()':
bridge.cpp:300:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  300 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:301:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  301 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37