oj.uz

Submission #677440

# Submission time Handle Problem Language Result Execution time Memory
677440 2023-01-03T11:09:57 Z onjo0127 None (JOI15_walls) C++11
10 / 100
 3000 ms 18656 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using ll = long long;

ll ans[200009];
int N, M, A[200009], B[200009], L[200009], R[200009], V[200009];
bool C[200009];

struct fenwick {
	ll F[200009];
	ll get(int x) {
		++x;
		ll s = 0;
		for(int i=x; i>=1; i-=(i&-i)) s += F[i];
		return s;
	}
	void upd(int x, int y) {
		++x;
		for(int i=x; i<=M; i+=(i&-i)) F[i] += y;
	}
} F1, F2;

int dst(int l, int r, int x) {
	if(x < l) return l-x;
	if(l <= x && x <= r) return 0;
	if(r < x) return x-r;
}

int main() {
	vector<int> W;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) {
		scanf("%d%d", &A[i], &B[i]);
		W.push_back(i);
	}
	sort(W.begin(), W.end(), [&](int p, int q) { return B[p] - A[p] < B[q] - A[q]; });
	vector<int> P;
	while(M--) {
		int x; scanf("%d", &x);
		int K = P.size();
		if(K <= 1) P.push_back(x);
		else {
			if(P[K-2] < P[K-1] && P[K-1] <= x) P.pop_back();
			else if(P[K-2] > P[K-1] && P[K-1] >= x) P.pop_back();
			P.push_back(x);
		}
	}
	M = P.size();
	set<int> S;
	priority_queue<tiii> pq;
	L[0] = R[0] = P[0]; C[0] = 1;
	for(int i=0; i<M; i++) {
		S.insert(i);
		if(i) {
			V[i] = max(P[i] - P[i-1], P[i-1] - P[i]);
			F1.upd(i, V[i]);
			F2.upd(i, +1);
			L[i] = min(L[i-1], P[i]);
			R[i] = max(R[i-1], P[i]);
			pq.push({-V[i], i-1, i});
		}
	}
	for(auto& it: W) {
		while(pq.size()) {
			int g, a, b; tie(g, a, b) = pq.top(); g = -g;
			if(C[a] || C[b]) {
				pq.pop();
				continue;
			}
			if(g > B[it] - A[it]) break;
			pq.pop();

			C[b] = 1; F1.upd(b, -V[b]); F2.upd(b, -1); S.erase(b);
			auto nt = S.upper_bound(b);
			if(nt != S.end()) {
				C[a] = 1; F1.upd(a, -V[a]); F2.upd(a, -1); S.erase(a);
				nt = S.upper_bound(b);
				auto pt = prev(nt);
				F1.upd(*nt, V[a] - V[b]); V[*nt] += V[a] - V[b];
				pq.push({-V[*nt], *pt, *nt});
			}
		}
		int l = 0, r = M-1, f = -1;
		while(l <= r) {
			int m = l+r >> 1;
			if(L[m] < A[it] || B[it] < R[m]) r = m-1, f = m;
			else l = m+1;
		}
		if(f == -1) continue;
		int x = f;
		while(1) {
			ans[it] += dst(A[it], B[it], P[x]);
			int d = 0;
			if(P[x] < A[it]) d = P[x] - A[it];
			if(B[it] < P[x]) d = P[x] - B[it];
			A[it] += d; B[it] += d;
			if(x == M-1) break;
			++x;
		}
		/*
		if(nt != S.end()) {
			int d = 0;
			if(P[f] < A[it]) d = P[f] - A[it];
			if(B[it] < P[f]) d = P[f] - B[it];
			ans[it] += dst(A[it] + d, B[it] + d, P[*nt]);
			ans[it] += F1.get(M-1) - F1.get(*nt) - (F2.get(M-1) - F2.get(*nt)) * (B[it] - A[it]);
		}
		*/
	}
	for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
	return 0;
}

Compilation message

walls.cpp: In function 'int main()':
walls.cpp:87:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |    int m = l+r >> 1;
      |            ~^~
walls.cpp: In function 'int dst(int, int, int)':
walls.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^
walls.cpp: In function 'int main()':
walls.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d%d", &A[i], &B[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
walls.cpp:41:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 121 ms 13692 KB Output is correct
3 Correct 175 ms 18520 KB Output is correct
4 Correct 158 ms 18656 KB Output is correct
5 Correct 209 ms 18512 KB Output is correct
6 Correct 114 ms 18488 KB Output is correct
7 Correct 125 ms 18448 KB Output is correct
8 Correct 20 ms 324 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1849 ms 2228 KB Output is correct
2 Execution timed out 3088 ms 13848 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 121 ms 13692 KB Output is correct
3 Correct 175 ms 18520 KB Output is correct
4 Correct 158 ms 18656 KB Output is correct
5 Correct 209 ms 18512 KB Output is correct
6 Correct 114 ms 18488 KB Output is correct
7 Correct 125 ms 18448 KB Output is correct
8 Correct 20 ms 324 KB Output is correct
9 Correct 1849 ms 2228 KB Output is correct
10 Execution timed out 3088 ms 13848 KB Time limit exceeded
11 Halted 0 ms 0 KB -