Submission #117558

#	Time	Username	Problem	Language	Result	Execution time	Memory
117558		ckodser	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	18 ms	6784 KiB

bridge

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
 
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 
 
using namespace :: std;
 
const ll maxn=2e5+500;
const ll inf=1e9+800;
 
 
vector<ll> comp;
ll fen[4][maxn];
 
void addFen(ll x,ll v,char c){
	for(x++;x<maxn;x+=(x&(-x))){
		fen[c][x]+=v;
	}
}
ll findFen(ll x,char c){
	ll ans=0;
	for(x++;x;x-=(x&(-x))){
		ans+=fen[c][x];
	}	
	return ans;
}
ll getVal(ll rx,ll x=-1){
	if(x==-1)x=lower_bound(comp.begin(),comp.end(),rx)-comp.begin();
	return (findFen(x,0)-findFen(x,2))*rx-findFen(x,1)+findFen(x,3);
}	
void add(pii a){
	ll sl=a.F;
	ll sr=a.S;
 
	ll l=lower_bound(comp.begin(),comp.end(),sl)-comp.begin();
	ll r=lower_bound(comp.begin(),comp.end(),sr)-comp.begin();
 
	addFen(r+1,1,0);
 
	addFen(r+1,sr,1);
 
	addFen(0,1,2);
	addFen(l,-1,2);
 
	addFen(0,sl,3);
	addFen(l,-sl,3);
}
ll getAns(){
	ll ans=inf*maxn;
	ll b=0;
	ll e=comp.size();
	while(e-b>10){
		ll mid=(e+b)/2;
		ans=min(ans,getVal(mid));
		ll x=findFen(mid,0);
		ll y=findFen(mid,2);
		if(x>y){
			e=mid;	
		}else{
			b=mid;
		}	
	}
	for(ll i=b;i<=e;i++){
		ans=min(ans,getVal(comp[i],i));
	}
	return ans;
}
void clearr(){
	memset(fen,0,sizeof fen);
}
 
 
ll n,k;
ll saf[maxn];
ll pre[maxn];
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	cin>>k>>n;
	ll sum=0;
	vector<pair<ll,pii> > vec;
	for(ll i=0;i<n;i++){
		char C,T;
		ll L,R;
		cin>>C>>L>>T>>R;
		if(R<L){
			swap(L,R);
		}
		sum+=(abs(R-L));
		if(C==T){
			n--;
			i--;
		}else{
			comp.pb(L);
			comp.pb(R);
			sum++;
			vec.pb(mp(L+R,mp(L,R)));
		}
	}
 	if(vec.size()==0){
		cout<<sum;
		return 0;
	}
	sort(comp.begin(),comp.end());
	auto it=unique(comp.begin(),comp.end());
	comp.resize(it-comp.begin());
 
	sort(vec.begin(),vec.end());
	clearr();
	for(ll i=0;i<(ll)vec.size();i++){
		pii e=vec[i].S;
		add(e);
		if(k==2){
			pre[i]=getAns();
		}
	}
	if(k==1){
		cout<<getAns()*2+sum<<endl;
		return 0;
	}
	clearr();
	for(ll i=(ll)vec.size()-1;i>=0;i--){
		pii e=vec[i].S;
		add(e);
		saf[i]=getAns();
	}
	ll ans=saf[0];
	for(ll i=1;i<n;i++){
		ans=min(ans,saf[i]+pre[i-1]);
	}
	cout<<2*ans+sum;
}

Compilation message (stderr)

bridge.cpp: In function 'void addFen(long long int, long long int, char)':
bridge.cpp:76:8: warning: array subscript has type 'char' [-Wchar-subscripts]
   fen[c][x]+=v;
        ^
bridge.cpp: In function 'long long int findFen(long long int, char)':
bridge.cpp:82:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   ans+=fen[c][x];
             ^

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