답안 #25073 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25073	2017-06-20T05:59:00 Z	김동현(#1052)	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	376 ms	17684 KB

bridge

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Lin{
	ll s, e;
	bool operator<(const Lin &oth) const {
		return s + e < oth.s + oth.e;
	}
};

const ll inf = 1e18;
int k, n, cnt;
ll v[200010];
Lin u[100010];
vector<ll> w;
ll ans, cans, lans, bs;

void t1(){
	scanf("%d", &n);
	for(int i = 1, x, y; i <= n; i++){
		char a[3], b[3];
		scanf("%s%d%s%d", a, &x, b, &y);
		if(a[0] == b[0]) ans += abs(x - y);
		else{
			w.push_back(x);
			w.push_back(y);
			ans++;
		}
	}
	sort(w.begin(), w.end());
	for(auto &i : w) ans += abs(i - w[w.size() / 2]);
	printf("%lld\n", ans);
}

const int sz = 200010;
struct BIT{
	ll dat[sz + 1];
	void upd(int x, ll v){ for(x++; x <= sz; x += x & -x) dat[x] += v; }
	ll get(int x){ ll ret = 0; for(x++; x; x -= x & -x) ret += dat[x]; return ret; }
	ll get(int s, int e){ if(s > e) return 0; return get(e) - get(s - 1); }
} B[2][3];

void upd(int i, int j, int x){
	B[j][0].upd(i, x);
	B[j][1].upd(i, -x * v[i]);
	B[j][2].upd(i, x * v[i]);
}

ll cal(int i, int j){
	return B[0][1].get(0, i) + B[0][0].get(0, i) * v[i] +
		   B[0][2].get(i + 1, sz - 1) - B[0][0].get(i + 1, sz - 1) * v[i] +
		   B[1][1].get(0, j) + B[1][0].get(0, j) * v[j] +
		   B[1][2].get(j + 1, sz - 1) - B[1][0].get(j + 1, sz - 1) * v[j];
}

void t2(){
	scanf("%d", &n);
	for(int i = 1, x, y; i <= n; i++){
		char a[3], b[3];
		scanf("%s%d%s%d", a, &x, b, &y);
		if(a[0] == b[0]) bs += abs(x - y);
		else{
			v[2 * cnt] = x;
			v[2 * cnt + 1] = y;
			u[cnt] = {x, y};
			bs++;
			cnt++;
		}
	}
	if(cnt == 0){
		printf("%lld\n", bs);
		return;
	}
	sort(v, v + 2 * cnt);
	sort(u, u + cnt);
	for(int t = 0; t < cnt; t++){
		Lin &i = u[t];
		i.s = (int)(lower_bound(v, v + 2 * cnt, i.s) - v);
		i.e = (int)(lower_bound(v, v + 2 * cnt, i.e) - v);
		//printf("%d - %d\n", i.s, i.e);
		upd(i.s, 1, 1); upd(i.e, 1, 1);
	}
	//puts("---");
	int i = 0, j = 0, k = 0;
	ans = lans = inf; cans = cal(i, j);
	for(; i < 2 * cnt; i++){
		j = max(i, j);
		while(k < cnt && v[u[k].s] + v[u[k].e] < v[i] + v[j]){
			//printf("upd %d\n", k);
			upd(u[k].s, 1, -1); upd(u[k].e, 1, -1);
			upd(u[k].s, 0, 1); upd(u[k].e, 0, 1);
			k++;
		}
		cans = cal(i, j);
		//printf("/// %d - %d : %lld\n", i, j, cans);
		ans = min(ans, cans);
		do{
			lans = cans;
			j++;
			if(j >= 2 * cnt) break;
			while(k < cnt && v[u[k].s] + v[u[k].e] < v[i] + v[j]){
				//printf("upd %d\n", k);
				upd(u[k].s, 1, -1); upd(u[k].e, 1, -1);
				upd(u[k].s, 0, 1); upd(u[k].e, 0, 1);
				k++;
			}
			cans = cal(i, j);
			ans = min(ans, cans);
			//printf("/// %d - %d : %lld\n", i, j, cans);
		}while(j < 2 * cnt && lans >= cans);
		j--;
		//puts("----");
	}
	printf("%lld\n", ans + bs);
}

int main(){
	scanf("%d", &k);
	if(k == 1) t1();
	else t2();
}

Compilation message

bridge.cpp: In function 'void t1()':
bridge.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bridge.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d", a, &x, b, &y);
                                  ^
bridge.cpp: In function 'void t2()':
bridge.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bridge.cpp:61:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d", a, &x, b, &y);
                                  ^
bridge.cpp: In function 'int main()':
bridge.cpp:119:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
                 ^

Subtask #1
8.0 / 8.0

#	결과	메모리	Grader output
1	Correct	14528 KB	Output is correct
2	Correct	14528 KB	Output is correct
3	Correct	14528 KB	Output is correct
4	Correct	14528 KB	Output is correct
5	Correct	14528 KB	Output is correct
6	Correct	14528 KB	Output is correct
7	Correct	14528 KB	Output is correct
8	Correct	14528 KB	Output is correct
9	Correct	14528 KB	Output is correct
10	Correct	14528 KB	Output is correct
11	Correct	14528 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14528 KB	Output is correct
2	Correct	0 ms	14528 KB	Output is correct
3	Correct	0 ms	14528 KB	Output is correct
4	Correct	0 ms	14528 KB	Output is correct
5	Correct	0 ms	14528 KB	Output is correct
6	Correct	0 ms	14528 KB	Output is correct
7	Correct	0 ms	14528 KB	Output is correct
8	Correct	0 ms	14528 KB	Output is correct
9	Correct	0 ms	14528 KB	Output is correct
10	Correct	0 ms	14528 KB	Output is correct
11	Correct	0 ms	14528 KB	Output is correct
12	Correct	43 ms	17684 KB	Output is correct
13	Correct	66 ms	17684 KB	Output is correct
14	Correct	39 ms	17684 KB	Output is correct
15	Correct	46 ms	16148 KB	Output is correct
16	Correct	29 ms	17684 KB	Output is correct
17	Correct	49 ms	17684 KB	Output is correct
18	Correct	43 ms	17684 KB	Output is correct
19	Correct	79 ms	17684 KB	Output is correct
20	Correct	36 ms	17684 KB	Output is correct
21	Correct	56 ms	17684 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	메모리	Grader output
1	Correct	14528 KB	Output is correct
2	Correct	14528 KB	Output is correct
3	Correct	14528 KB	Output is correct
4	Correct	14528 KB	Output is correct
5	Correct	14528 KB	Output is correct
6	Correct	14528 KB	Output is correct
7	Correct	14528 KB	Output is correct
8	Correct	14528 KB	Output is correct
9	Correct	14528 KB	Output is correct
10	Correct	14528 KB	Output is correct
11	Correct	14528 KB	Output is correct
12	Correct	14528 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	메모리	Grader output
1	Correct	14528 KB	Output is correct
2	Correct	14528 KB	Output is correct
3	Correct	14528 KB	Output is correct
4	Correct	14528 KB	Output is correct
5	Correct	14528 KB	Output is correct
6	Correct	14528 KB	Output is correct
7	Correct	14528 KB	Output is correct
8	Correct	14528 KB	Output is correct
9	Correct	14528 KB	Output is correct
10	Correct	14528 KB	Output is correct
11	Correct	14528 KB	Output is correct
12	Correct	14528 KB	Output is correct
13	Correct	14528 KB	Output is correct
14	Correct	14528 KB	Output is correct
15	Correct	14528 KB	Output is correct
16	Correct	14528 KB	Output is correct
17	Correct	14528 KB	Output is correct
18	Correct	14528 KB	Output is correct
19	Correct	14528 KB	Output is correct
20	Correct	14528 KB	Output is correct
21	Correct	14528 KB	Output is correct
22	Correct	14528 KB	Output is correct
23	Correct	14528 KB	Output is correct
24	Correct	14528 KB	Output is correct

Subtask #5
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	14528 KB	Output is correct
2	Correct	0 ms	14528 KB	Output is correct
3	Correct	0 ms	14528 KB	Output is correct
4	Correct	0 ms	14528 KB	Output is correct
5	Correct	0 ms	14528 KB	Output is correct
6	Correct	0 ms	14528 KB	Output is correct
7	Correct	0 ms	14528 KB	Output is correct
8	Correct	0 ms	14528 KB	Output is correct
9	Correct	0 ms	14528 KB	Output is correct
10	Correct	0 ms	14528 KB	Output is correct
11	Correct	0 ms	14528 KB	Output is correct
12	Correct	0 ms	14528 KB	Output is correct
13	Correct	0 ms	14528 KB	Output is correct
14	Correct	0 ms	14528 KB	Output is correct
15	Correct	0 ms	14528 KB	Output is correct
16	Correct	0 ms	14528 KB	Output is correct
17	Correct	0 ms	14528 KB	Output is correct
18	Correct	0 ms	14528 KB	Output is correct
19	Correct	0 ms	14528 KB	Output is correct
20	Correct	0 ms	14528 KB	Output is correct
21	Correct	3 ms	14528 KB	Output is correct
22	Correct	0 ms	14528 KB	Output is correct
23	Correct	0 ms	14528 KB	Output is correct
24	Correct	0 ms	14528 KB	Output is correct
25	Correct	139 ms	14528 KB	Output is correct
26	Correct	193 ms	14528 KB	Output is correct
27	Correct	313 ms	14528 KB	Output is correct
28	Correct	376 ms	14528 KB	Output is correct
29	Correct	296 ms	14528 KB	Output is correct
30	Correct	173 ms	14528 KB	Output is correct
31	Correct	183 ms	14528 KB	Output is correct
32	Correct	173 ms	14528 KB	Output is correct
33	Correct	173 ms	14528 KB	Output is correct
34	Correct	219 ms	14528 KB	Output is correct
35	Correct	149 ms	14528 KB	Output is correct
36	Correct	189 ms	14528 KB	Output is correct
37	Incorrect	186 ms	14528 KB	Output isn't correct

답안 #25073

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
0 / 37.0