Submission #259348

#	Time	Username	Problem	Language	Result	Execution time	Memory
259348		shayan_p	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2083 ms	3560 KiB

bridge

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 1e5 + 10, inf = 1e9 + 10;
const ll INF = 1e18;

ll sv[maxn];

vector<pii> vec;
int LST;
vector<int> arr;

void restart(){
    vec.clear();
    LST = -1;
}
ll calc(int pos){
    ll num = 0;
    for(pii p : vec){
	if(pos < p.F)
	    num+= p.F - pos;
	if(p.S < pos)
	    num+= pos - p.S;
    }
    return num;
}
ll add(int f, int s){
    vec.PB({f, s});
    int l = -1, r = sz(arr)-1;
    while(r-l > 1){
	int mid = (l + r) >> 1;
	if(calc(arr[mid]) > calc(arr[mid+1]))
	    l = mid;
	else
	    r = mid;	
    }
    assert(LST <= r);
    LST = r;
    return calc(arr[r]) * 2;

}


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

    int k, n;
    cin >> k >> n;
    ll sig = 0;
    vector<pii> inp;
    for(int i = 0; i < n; i++){
	char a, b;
	int l, r;
	cin >> a >> l >> b >> r;
	if(r < l)
	    swap(l, r);
	sig+= r-l;
	if(a != b){
	    sig++;
	    inp.PB({l, r});
	}
    }
    sort(inp.begin(), inp.end(), [](pii a, pii b){ return a.F + a.S < b.F + b.S; } );
    n = sz(inp);

    for(int i = 0; i < n; i++){
	arr.PB(inp[i].F);
	arr.PB(inp[i].S);
    }
    
    sort(arr.begin(), arr.end());
    arr.resize( unique(arr.begin(), arr.end()) - arr.begin() );
    
    restart();
    for(int i = 0; i < n; i++){
	sv[i + 1] = add(inp[i].F, inp[i].S);
    }
    for(int i = 0; i < sz(arr); i++){
	arr[i]*=-1;
    }
    reverse(arr.begin(), arr.end());
    restart();    
    ll ans = INF;
    for(int i = n-1; i >= 0; i--){
	ans = min(ans, sig + sv[i] + add(-inp[i].S, -inp[i].F));
    }
    if(k == 1)
	ans = sig + sv[n];
    return cout << ans << endl, 0;
    
}

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