Submission #879553

#	Time	Username	Problem	Language	Result	Execution time	Memory
879553		Shayan86	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	203 ms	20812 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 50;
const ll Mod = 1e9 + 7;

ll n, m, k, pre[N], nxt[N], val[N], cnt, med, ans, pref[N], suf[N];

set<pii> ms;
vector<pii> vec;

bool cmp(pii i, pii j){
    return (i.F + i.S) < (j.F + j.S);
}

void add(int x){
    int aft = ms.lower_bound(Mp(x, ++cnt)) -> S;
    ms.insert(Mp(x, cnt));

    val[cnt] = x; pre[cnt] = pre[aft]; nxt[pre[cnt]] = cnt; nxt[cnt] = aft; pre[aft] = cnt;
    ans += abs(val[med] - x);

    if(cnt % 2 == 0 && x < val[med]){
        med = pre[med];
    }
    if(cnt % 2 == 1 && x >= val[med]){
        ans -= val[nxt[med]] - val[med];
        med = nxt[med];
    }
}

int main(){
    fast_io;

    cin >> k >> n;

    ll sum = 0;
    for(int i = 1; i <= n; i++){
        char p, q; int s, t;
        cin >> p >> s >> q >> t;
        if(p != q){
            vec.pb(Mp(s, t)); sum++;
        }
        else sum += abs(s - t);
    }
    if(vec.empty()) kill(sum);

    vec.pb(Mp(-1, -1));
    sort(all(vec), cmp);

    cnt = 2;
    nxt[1] = 2; pre[2] = 1;
    val[1] = -1; val[2] = Mod;
    ms.insert(Mp(val[1], 1));
    ms.insert(Mp(val[2], 2));
    med = 1; ans = 0;

    m = vec.size() - 1; pref[0] = 0;
    for(int i = 1; i <= m; i++){
        add(vec[i].F); add(vec[i].S);
        pref[i] = ans;
    }

    fill(pre, pre + N, 0);
    fill(nxt, nxt + N, 0);
    ms.clear();

    cnt = 2;
    nxt[1] = 2; pre[2] = 1;
    val[1] = -1; val[2] = Mod;
    ms.insert(Mp(val[1], 1));
    ms.insert(Mp(val[2], 2));
    med = 1; ans = 0;

    suf[m+1] = 0;
    for(int i = m; i > 0; i--){
        add(vec[i].F); add(vec[i].S);
        suf[i] = ans;
    }

    ll res = pref[m];
    if(k == 1) kill(res + sum);

    for(int i = 1; i < m; i++) res = min(res, pref[i] + suf[i+1]);
    kill(res + sum);

}

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