Submission #1282000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282000		swishy123	Palembang Bridges (APIO15_bridge)	C++20	49 / 100	2095 ms	82692 KiB

bridge

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int def = 1e6+1;
const int maxk = 18;
const ll inf = 1e18;

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, tl, tr;
    int l, r;

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

vector<Node> st;
void extend(int u){
    int tl = st[u].tl, tr = st[u].tr;
    int l = st[u].l, r = st[u].r;
    
    if (tl == tr) return;
    int mid = (tl + tr) / 2;

    if (l == -1){
        st[u].l = st.size();
        st.push_back(Node(tl, mid));
    }
    if (r == -1){
        st[u].r = st.size();
        st.push_back(Node(mid + 1, tr));
    }
}       
void push(int u){
    ll lazy = st[u].lazy;
    int l = st[u].l, r = st[u].r;

    if (l != -1){
        st[l].sum += (st[l].tr - st[l].tl + 1) * lazy;
        st[l].lazy += lazy;
    }
    if (r != -1){
        st[r].sum += (st[r].tr - st[r].tl + 1) * lazy;
        st[r].lazy += lazy;
    }
    st[u].lazy = 0;
}   

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

    update(ql, qr, st[crr].l, x);
    update(ql, qr, st[crr].r, x);

    st[crr].sum = st[st[crr].l].sum + st[st[crr].r].sum;
}

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

    return get(ql, qr, st[crr].l) + get(ql, qr, st[crr].r);
}

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

    ll add = 0;
    vector<Segment> sm;

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

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

    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++){
        st.clear();
        st.push_back(Node(0, bound));

        for (int i = 1; i <= n; i++){
            int l = sm[i - 1].l, r = sm[i - 1].r;   
            update(0, 0, 0, (r - l) + l * 2 + 2);
            update(0, l, 0, -2);
            update(r + 1, bound, 0, 2);

            l = 0, r = 1e9;
            while (r - l > 3){
                int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
                ll val1 = get(0, mid1, 0), val2 = get(0, mid2, 0);
    
                if (val1 <= val2)
                    r = mid2;
                else
                    l = mid1;
            }
            for (int j = l; j <= r; j++)
                pref[i] = min(pref[i], get(0, 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;
    }
}

/*
0 0 0 0 0
*/

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 = 1;
    while (t--){
        solve();
        cout << "\n";
    }
}

Compilation message (stderr)

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

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