Submission #21833

#	Time	Username	Problem	Language	Result	Execution time	Memory
21833		gs12117	Palembang Bridges (APIO15_bridge)	C++11	100 / 100	1096 ms	11748 KiB

bridge

#include<stdio.h>
#include<algorithm>
#include<queue>
int p, tn;
long long int ansd;
struct psn {
	int a, b;
	bool operator<(const psn&r)const {
		return a + b < r.a + r.b;
	}
};
psn pl[100100];
int n;
long long int dp[3][100100];
int cmin[3][100100];
int sl[100100];
long long int ans;
struct pqn {
	int x;
	int idx;
	bool operator<(const pqn&r)const {
		return x < r.x;
	}
};
int dist(int x, int y) {
	if (x < y)return y - x;
	return x - y;
}
int main() {
	scanf("%d%d", &p, &tn);
	for (int i = 0; i < tn; i++) {
		char ap[10];
		char bp[10];
		int a, b;
		scanf("%s%d%s%d", ap, &a, bp, &b);
		if (ap[0] == bp[0]) {
			ansd += dist(a, b);
		}
		else {
			pl[n].a = a;
			pl[n].b = b;
			n++;
		}
	}
	std::sort(pl, pl + n);
	for (int i = 1; i <= n; i++) {
		dp[0][i] = 1e17;
	}
	for (int z = 0; z < p; z++) {
		dp[z + 1][0] = 0;
		cmin[z + 1][0] = 0;
		for (int ii = 17; ii >= 0; ii--) {
			std::priority_queue<pqn> l, r;
			long long int s = 0;
			int j = 0;
			int il, ir;
			il = 0;
			ir = 0;
			int bi = 0;
			for (int ti = (1 << ii); ti <= n; ti += (1 << (ii + 1))) {
				for (int i = bi; i < ti; i++) {
					sl[i] = 0;
					if (l.size() == 0 || l.top().x >= pl[i].a) {
						pqn t;
						t.idx = i;
						t.x = pl[i].a;
						l.push(t);
						sl[i]++;
					}
					else {
						pqn t;
						t.idx = i;
						t.x = -pl[i].a;
						r.push(t);
					}
					if (l.top().x >= pl[i].b) {
						pqn t;
						t.idx = i;
						t.x = pl[i].b;
						l.push(t);
						sl[i]++;
					}
					else {
						pqn t;
						t.idx = i;
						t.x = -pl[i].b;
						r.push(t);
					}
					s += dist(pl[i].a, l.top().x);
					s += dist(pl[i].b, l.top().x);
					if (l.size() - il > r.size() - ir) {
						pqn t = l.top();
						t.x = -t.x;
						sl[t.idx]--;
						r.push(t);
						l.pop();
					}
					if (l.size() - il < r.size() - ir) {
						s += r.top().x + l.top().x;
						s += r.top().x + l.top().x;
						pqn t = r.top();
						t.x = -t.x;
						sl[t.idx]++;
						l.push(t);
						r.pop();
					}
					while (l.top().idx < j) {
						il--;
						l.pop();
					}
					while (r.top().idx < j) {
						ir--;
						r.pop();
					}
				}
				bi = ti;
				int mj;
				if (ti + (1 << ii) > n)mj = ti;
				else mj = cmin[z + 1][ti + (1 << ii)];
				if (mj >= ti)mj = ti - 1;
				dp[z + 1][ti] = s;
				cmin[z + 1][ti] = j;
				while (j < mj) {
					s += dp[z][j + 1] - dp[z][j];
					s -= dist(pl[j].a, l.top().x);
					s -= dist(pl[j].b, l.top().x);
					if (pl[j].a <= l.top().x&&pl[j].b <= l.top().x) {
						s += r.top().x + l.top().x;
						s += r.top().x + l.top().x;
					}
					il += sl[j];
					ir += 2 - sl[j];
					j++;
					while (l.size() > 0 && l.top().idx < j) {
						il--;
						l.pop();
					}
					while (r.size() > 0 && r.top().idx < j) {
						ir--;
						r.pop();
					}
					if (l.size() - il > r.size() - ir) {
						pqn t = l.top();
						t.x = -t.x;
						sl[t.idx]--;
						r.push(t);
						l.pop();
					}
					if (l.size() - il < r.size() - ir) {
						pqn t = r.top();
						t.x = -t.x;
						sl[t.idx]++;
						l.push(t);
						r.pop();
					}
					while (l.top().idx < j) {
						il--;
						l.pop();
					}
					while (r.top().idx < j) {
						ir--;
						r.pop();
					}
					if (dp[z + 1][ti] > s) {
						dp[z + 1][ti] = s;
						cmin[z + 1][ti] = j;
					}
				}
			}
		}
	}
	ans = dp[p][n] + ansd + n;
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:30:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &p, &tn);
                        ^
bridge.cpp:35:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%s%d", ap, &a, bp, &b);
                                    ^

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