Submission #25160

#	Time	Username	Problem	Language	Result	Execution time	Memory
25160		suhgyuho_william	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	983 ms	12728 KiB

bridge

#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,nn;
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];
vector<int> Value;
struct SEG{
	lld sum,cnt;
}seg[300002];

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);
	}
}
int change(int x){
	return lower_bound(Value.begin(),Value.end(),x)-Value.begin()+1;
}
SEG getseg(int node,int l,int r,int s,int e){
	if(r < s || e < l || s > e) return {0,0};
	if(s <= l && r <= e) return seg[node];
	int mid = (l+r)/2;
	SEG tmp1,tmp2;
	tmp1 = getseg(node*2,l,mid,s,e);
	tmp2 = getseg(node*2+1,mid+1,r,s,e);
	tmp1.sum += tmp2.sum; tmp1.cnt += tmp2.cnt;
	return tmp1;
}
SEG get2(lld s,lld e){
	int it1,it2;
	it1 = change(s); it2 = change(e+1);
	if(it2 == 1) return {0,0};
	it2--;
	return getseg(1,1,nn,it1,it2);
}
lld get(){
	int mid = X[t1]+X[t2];
	SEG tmp1,tmp2;
	tmp1 = get2((X[t1]+1)*2,mid);
	tmp2 = get2(mid+1,((X[t2]-1)*2));
	lld tsum = 0;
	tsum += (tmp1.sum-tmp1.cnt*2*X[t1]);
	tsum += (tmp2.cnt*2*X[t2]-tmp2.sum);
	return tsum;
}
void update(int x,int add){
	int value = Value[x-1];
	x += (nn-1);
	while(x){
		seg[x].sum += value*add;
		seg[x].cnt += add;
		x /= 2;
	}
}
void addt2(){
	t2++;
    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
		update(change(in[b[ty2].num].x+in[b[ty2].num].y),1);
		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
		update(change(in[b[i].num].x+in[b[i].num].y),-1);
		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*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{
				//seg update
				update(change(in[a[tx].num].x+in[a[tx].num].y),-1);
				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;
			Value.pb(x+y);
		}
	}
	N = rear; ans = LINF;
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	sort(Value.begin(),Value.end());
	Value.erase(unique(Value.begin(),Value.end()),Value.end());
	for(nn=1; nn<Value.size(); nn*=2);
	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;
}

Compilation message (stderr)

bridge.cpp: In function 'void process1()':
bridge.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<X.size(); i++){
                ^
bridge.cpp: In function 'void process2()':
bridge.cpp:144:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t2 == X.size()-1) break;
         ^
bridge.cpp:153:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(t1+1 < X.size()-1){
             ^
bridge.cpp:178:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(t2 == X.size()-1) break;
          ^
bridge.cpp: In function 'int main()':
bridge.cpp:214:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(nn=1; nn<Value.size(); nn*=2);
              ^
bridge.cpp:192:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&K,&N);
                      ^
bridge.cpp:196:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c %d %c %d",&op1,&x,&op2,&y);
                                         ^

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