QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94862#5669. Traveling in Jade CitySEM_PRESSAO_pedroteosousa#ML 2ms5508kbC++234.5kb2023-04-08 01:21:132023-04-08 01:21:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-08 01:21:15]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:5508kb
  • [2023-04-08 01:21:13]
  • 提交

answer

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

using ll = long long;
#define int ll
#define all(v) v.begin(),v.end()
#define pb push_back

void dbg_out() {cerr << endl; }
template< typename H, typename... T> 
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const int N = 1e6 + 10;

int n, k, m, q, c[N], x[N];

void solve () {
	// u, 1, k, v
	// u, k, 1, v
	// u, v
	// u, 1, v
	// u, k, v	
	cin >> n >> k >> m >> q;
	for (int i = 1; i <= n; i++) cin >> c[i];
	for (int i = 0; i <= m; i++) cin >> x[i];

	int L = 0, M = 0, R = 0;
	vector dist (n, vector<int> (n + m + 1));
	{
		int cur = 0;
		for (int i = 1; i < k; i++) {
			cur += c[i];
			dist[0][i + 1] = cur;
		}
		R = cur;
	}
	{
		int cur = 0;
		for (int i = 0; i < m; i++) {
			cur += x[i];
			dist[0][n + i + 1] = cur;
		}
		M = cur + x[m];
	}
	{
		int cur = 0;
		for (int i = n; i >= k; i--) {
			cur += c[i];
			dist[0][i] = cur;
		}
		L = cur;
	}

	// vamos calcular agora a distancia para k
	{
		int cur = 0;
		for (int i = k - 1; i >= 1; i--) {
			cur += c[i];
			dist[1][i] = cur;
		}
	}
	{
		int cur = 0;
		for (int i = k + 1; i <= n; i++) {
			cur += c[i - 1];
			dist[1][i] = cur;
		}
	}
	{
		int cur = 0;
		for (int i = n + m; i >= n + 1; i--) {
			cur += x[i - n];
			dist[1][i] = cur;
		}
	}

	// dbg (L, M, R);
	// for (int i = 1; i <= n + m; i++) cout << dist[0][i] << " ";
	// cout << "\n";
	// for (int i = 1; i <= n + m; i++) cout << dist[1][i] << " ";
	// cout << "\n";

	set<int> esq, meio, dir;
	const int INF = 1e17;

	while (q--) {
		char op; cin >> op;

		if (op == 'x') {
			int j; cin >> j;
			if (meio.find (j) != meio.end ()) meio.erase (j);
			else meio.insert (j);
		}
		else if (op == 'c') {
			int j; cin >> j;
			if (j < k) {
				if (dir.find (j) != dir.end ()) dir.erase (j);
				else dir.insert (j);
			}
			else {
				if (esq.find (j) != esq.end ()) esq.erase (j);
				else esq.insert (j);
			}
		}
		else {

			auto find_path = [&] (int u, int pivot) -> bool {
				// vamos tentar ir do u para pivot
				if (u == pivot) return 1;
				if (pivot == 1) {
					if (u < k) return !dir.size () || *dir.begin () >= u;
					else if (u <= n) return !esq.size () || *--esq.end () < u;
					else return !meio.size () || *meio.begin () >= u - n;
				}
				else {
					if (u < k) return !dir.size () || *--dir.end () < u;
					else if (u <= n) return !esq.size () || *esq.begin () >= u;
					else return !meio.size () || *--meio.end () < u - n;
				}
			};
			
			int u, v; cin >> u >> v;
			if (u > v) swap (u, v);
			int ans = INF;

			// vamos tentar ir direto
			if (1 < u && v < k) {
				// se estao na direita!
				auto it = dir.lower_bound (u);
				if (it == dir.end () || *it >= v) ans = min (ans, dist[0][v] - dist[0][u]);
			}
			if (k < u && v <= n) {
				// se estao na esquerda!
				auto it = esq.lower_bound (u);
				if (it == esq.end () || *it >= v) ans = min (ans, dist[1][v] - dist[1][u]);
			}
			if (n + 1 <= u && v <= n + m) {
				// se estao no meio
				auto it = meio.lower_bound (u - n);
				if (it == meio.end () || *it >= v) ans = min (ans, dist[0][v] - dist[0][u]);
			}

			// se consigo fazer u -> 1
			if (u != k) {
				int cur = 0;
				if (find_path (u, 1)) {
					cur += dist[0][u];
					// tentamos ir direto para v
					if (find_path (v, 1)) {
						ans = min (ans, cur + dist[0][v]);
					}
					// tentamos ir para k
					int bridge = INF;
					if (!esq.size ()) bridge = min (bridge, L);
					if (!dir.size ()) bridge = min (bridge, R);
					if (!meio.size ()) bridge = min (bridge, M);

					if (bridge != INF) {
						cur += bridge;
						if (find_path (v, k)) {
							ans = min (ans, cur + dist[1][v]);
						}
					}
				}  
			}
			else {
				int cur = 0;
				if (find_path (u, k)) {
					cur += dist[1][u];
					// tentamos ir direto para v
					if (find_path (v, k)) {
						ans = min (ans, cur + dist[1][v]);
					}
					// tentamos ir para k
					int bridge = INF;
					if (!esq.size ()) bridge = min (bridge, L);
					if (!dir.size ()) bridge = min (bridge, R);
					if (!meio.size ()) bridge = min (bridge, M);

					if (bridge != INF) {
						cur += bridge;
						if (find_path (v, 1)) {
							ans = min (ans, cur + dist[0][v]);
						}
					}
				}  
			}
			if (ans == INF) cout << "impossible\n";
			else cout << ans << "\n";
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5508kb

input:

4 3 1 9
2 3 8 4
1 1
q 3 4
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4

output:

6
8
9
impossible
6

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 5368kb

input:

4 3 1 9
2 3 8 4
1 1
q 3 4
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4

output:

6
8
9
impossible
6

result:

ok 5 lines

Test #3:

score: -100
Memory Limit Exceeded

input:

1000000 999999 1000000 1000000
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 2...

output:


result: