Submission #926001

#	Time	Username	Problem	Language	Result	Execution time	Memory
926001		treap_enjoyer	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	115 ms	2392 KiB

bridge

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define all(x) x.begin(), x.end()
#define ld long double
#define pii pair<int, int>

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
struct st{
    bool a;
    bool b;
    int x;
    int y;
};
int n;
vector<st> a;
long long calc(int pos){
    ll d = 0;
    for(int i = 1; i <= n; i++){
        if(a[i].a != a[i].b){
            if(pos < a[i].x) d += (a[i].x - pos) * 2;
            if(pos > a[i].y) d += (pos - a[i].y) * 2;
            d += a[i].y - a[i].x + 1;
        }
        else d += a[i].y - a[i].x;
    }
    return d;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");
    int k;
    cin >> k >> n;
    a.resize(n + 1);
    {
    char a1, b1;
    for(int i = 1; i <= n; i++){
        cin >> a1 >> a[i].x >> b1 >> a[i].y;
        a[i].a = a1 - 'A';
        a[i].b = b1 - 'A';
        if(a[i].x > a[i].y) swap(a[i].x, a[i].y);
    }
    }
    int l = 0, r = 1e9;
    ll ans = 1e18;
    while(l <= r){
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        ans = min(ans, calc(m1));
        ans = min(ans, calc(m2));
        if(calc(m1) < calc(m2)){
            r = m2 - 1;
        }
        else{
            l = m1 + 1;
        }
    }
    for(int i = l; i <= r; i++){
        ans = min(ans, calc(i));
    }
    cout << ans << endl;
}

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