oj.uz

답안 #25108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25108 2017-06-20T07:04:54 Z 서규호(#1053) Palembang Bridges (APIO15_bridge) C++14
0 / 100
 0 ms 4376 KB 
#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);
	}
}
void undo(){
	for(int i=btx2+1; i<=tx2; i++) cnt2++;
	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));
	}
	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());
	for(int i=1; i<X.size()-1; i++){
		if(t2 == t1+1) addt2();
		//t1++
		t1++;
		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));
			}
		}
		while(1){
			if(ty == N || a[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;
}

Compilation message

bridge.cpp: In function 'void process1()':
bridge.cpp:38: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:102:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(t2 == X.size()-1) break;
         ^
bridge.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<X.size()-1; i++){
                ^
bridge.cpp:131: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:144:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
                                   ^
bridge.cpp:145: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:149: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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 4376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 4376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 4376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 4376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 4376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -