| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 25153 | suhgyuho_william | Palembang Bridges (APIO15_bridge) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 10007
#define left lleft
#define right rright
#define INF 2000000000
#define LINF 1000000000000000000LL
#define next nnext
using namespace std;
int N,K,rear;
int tx,ty,tx2,ty2,btx2,bty2,t1,t2;
lld memo,ans,sum,bsum;
lld cnt1,cnt2,cnt3,cnt4;
vector<lld> X;
struct IN{
int x,y;
}in[100002];
struct data{
int x,num;
}a[100002],b[100002];
multiset<lld> S;
void process1(){
for(int i=1; i<=N; i++){
sum += (a[i].x+b[i].x-X[0]-X[0]);
if(a[i].x > X[0]) cnt2++;
}
ans = min(ans,sum);
while(1){
if(tx == N || a[tx+1].x > X[0]) break;
tx++;
}
for(int i=1; i<X.size(); i++){
sum += (2*cnt1*(X[i]-X[i-1])); sum -= (2*cnt2*(X[i]-X[i-1]));
while(1){
if(tx == N || a[tx+1].x > X[i]) break;
tx++;
cnt2--;
}
while(1){
if(ty == N || b[ty+1].x > X[i-1]) break;
ty++;
cnt1++; sum += (X[i]-X[i-1])*2;
}
ans = min(ans,sum);
}
}
lld get(){
lld tsum = 0;
for(auto &i : S) tsum += min(i-X[t1]*2,2*X[t2]-i);
return tsum;
}
void addt2(){
t2++;
sum += (2*cnt1*(X[t2]-X[t2-1])); sum -= (2*cnt2*(X[t2]-X[t2-1]));
btx2 = tx2; bty2 = ty2;
while(1){
if(tx2 == N || a[tx2+1].x > X[t2]) break;
tx2++;
cnt2--;
}
while(1){
if(ty2 == N || b[ty2+1].x > X[t2-1]) break;
ty2++;
if(in[b[ty2].num].x <= X[t1]) continue;
//segupdate
S.insert(in[b[ty2].num].x+in[b[ty2].num].y);
int x,y;
x = in[b[ty2].num].x; y = in[b[ty2].num].y;
sum -= (y-x);
}
}
void undo(){
for(int i=bty2+1; i<=ty2; i++){
if(in[b[i].num].x <= X[t1]) continue;
//segupdate
S.erase(S.find(in[b[i].num].x+in[b[i].num].y));
int x,y;
x = in[b[i].num].x; y = in[b[i].num].y;
sum += (y-x);
}
cnt2 += (tx2-btx2);
tx2 = btx2; ty2 = bty2;
sum -= (2*cnt1*(X[t2]-X[t2-1])); sum += (2*cnt2*(X[t2]-X[t2-1]));
t2--;
}
void process2(){
for(int i=1; i<=N; i++){
sum += (a[i].x+b[i].x-X[0]-X[0]);
if(a[i].x > X[0]) cnt2++;
}
if(X.size() <= 1){
ans = sum;
return;
}
while(1){
if(tx == N || a[tx+1].x > X[0]) break;
tx++; tx2++;
}
while(1){
if(t2 == X.size()-1) break;
bsum = sum+get();
addt2();
if(sum+get() > bsum){
undo();
break;
}
}
ans = min(ans,sum+get());
while(t1+1 < X.size()-1){
if(t2 == t1+1) addt2();
//t1++
t1++;
sum += (2*cnt1*(X[t1]-X[t1-1]));
while(1){
if(tx == N || a[tx+1].x > X[t1]) break;
tx++;
if(in[a[tx].num].y >= X[t2]) continue;
else{
S.erase(S.find(in[a[tx].num].x+in[a[tx].num].y));
int x,y;
x = in[a[tx].num].x; y = in[a[tx].num].y;
sum += (y-x);
}
}
while(1){
if(ty == N || b[ty+1].x > X[t1-1]) break;
ty++;
cnt1++;
sum += (2*(X[t1]-X[t1-1]));
}
while(1){
if(t2 == X.size()-1) break;
bsum = sum+get();
addt2();
if(sum+get() > bsum){
undo();
break;
}
}
ans = min(ans,sum+get());
}
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d %d",&K,&N);
for(int i=1; i<=N; i++){
int x,y;
char op1,op2;
scanf("\n%c %d %c %d",&op1,&x,&op2,&y);
if(x > y) swap(x,y);
if(op1 == op2) memo += (y-x);
else{
rear++;
a[rear].x = x; a[rear].num = rear;
b[rear].x = y; b[rear].num = rear;
X.pb(x); X.pb(y);
memo++;
in[rear].x = x; in[rear].y = y;
}
}
N = rear; ans = LINF;
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
sort(a+1,a+N+1,[&](data &x,data &y){
return x.x < y.x;
});
sort(b+1,b+N+1,[&](data &x,data &y){
return x.x < y.x;
});
if(K == 1) process1();
else process2();
ans += memo;
printf("%lld\n",ans);
return 0;
}