| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 117522 | ckodser | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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(ll i=x;i<maxn;i++){
fen[c][i]+=v;
}
return;
for(x++;x<maxn;x+=(x&(-x))){
fen[c][x]+=v;
}
}
ll findFen(ll x,char c){
return fen[c][x];
ll ans=0;
for(x++;x;x-=(x&(-x))){
ans+=fen[c][x];
}
return ans;
}
ll getVal(ll rx){
ll 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;
for(auto e:comp){
ans=min(ans,getVal(e));
}
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;
sum+=(abs(R-L));
if(C!=T){
comp.pb(L);
comp.pb(R);
sum++;
vec.pb(mp(L+R,mp(L,R)));
}
}
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=