oj.uz

Submission #529527

# Submission time Handle Problem Language Result Execution time Memory
529527 2022-02-23T06:02:33 Z LucaDantas Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 418 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

constexpr int maxn = 4e5+10, inf = 0x3f3f3f3f;

struct PersistentSegmentTree {
	struct Node {
		Node *l, *r;
		int val;
		Node() : l(this), r(this), val(0) {}
	};
	int t = 0;
	Node *root[maxn]; // we have a root for each version of the seg
	
	PersistentSegmentTree() { root[0] = new Node(); }

	void upd(int pos) {
		++t;
		root[t] = upd(root[t-1], 1, inf, pos);
	}

	Node* upd(Node *node, int i, int j, int pos) { // add v to interval l, r
		/* printf("%lld %lld\n", i, j);
		fflush(stdout); */

		Node *aq = new Node();
		*aq = *node;
		
		aq->val++;

		if(i == j) return aq;

		int m = (i+j) >> 1;
		if(pos <= m)
			aq->l = upd(aq->l, i, m, pos);
		else
			aq->r = upd(aq->r, m+1, j, pos);

		return aq;
	}

	int query(Node *node, int i, int j, int l, int r) { // query the interval [l, r] on this version of the seg
		if(i > r || j < l) return 0;
		if(i >= l && j <= r) return node->val;
		int m = (i+j) >> 1;
		return query(node->l, i, m, l, r) + query(node->r, m+1, j, l, r);
	}

	int last(Node *L, Node *R, int i, int j) {
		if(R->val - L->val == 0) return 0; // trocar pra 0 DEBUG <----------------------------------------->
		if(i == j) return i;
		
		int m = (i+j) >> 1;
		
		int qr = last(L->r, R->r, m+1, j);
		if(qr != 0) return qr; // trocar pra 0 DEBUG <----------------------------------------------------->

		return last(L->l, R->l, i, m);
	}
} segX, segTime;

int A[maxn], B[maxn];
pair<int,int> X[maxn];

int32_t main() {
	int n, k; scanf("%lld %lld", &n, &k);
	
	for(int i = 1; i <= n; i++)
		scanf("%lld %lld", A+i, B+i);

	for(int i = 1; i <= k; i++) {
		int x; scanf("%lld", &x); X[i] = {x, i};
		segTime.upd(x);
	}

	sort(X+1, X+k+1);
	for(int i = 1; i <= k; i++) {
		segX.upd(X[i].second);
	}

	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		int a = A[i], b = B[i];
		if(a > b) swap(a, b);
		// quero achar o evento com o maior tempo tal que o valor dele está contido em [a, b[
		int last = 0;
		if(a != b) {
			int itL = (lower_bound(X+1, X+1+k, pair<int,int>(a, -1)) - X) - 1;
			int itR = (lower_bound(X+1, X+1+k, pair<int,int>(b, -1)) - X) - 1;
			
			// printf("%lld %lld -> %lld %lld\n", a, b, itL, itR);
			last = segX.last(segX.root[itL], segX.root[itR], 1, inf);
		} else last = 0;

		/* printf("%lld %lld -> %lld %lld %lld\n", a, b, last, segTime.query(segTime.root[segTime.t], 1, inf, b, inf), segTime.query(segTime.root[segTime.t], 1, inf, b, inf) - 
				segTime.query(segTime.root[last], 1, inf, b, inf)); // >= b */

		if(last != 0)
			ans += (segTime.query(segTime.root[segTime.t], 1, inf, b, inf) -
					segTime.query(segTime.root[last], 1, inf, b, inf)) % 2 == 0 ? b : a;
			/* printf("%lld\n", segTime.query(segTime.root[segTime.t], 1, inf, b, inf) -
					segTime.query(segTime.root[last], 1, inf, b, inf) % 2 == 0 ? b : a); */
		else
			ans += segTime.query(segTime.root[segTime.t], 1, inf, b, inf) % 2 == 0 ? A[i] : B[i];
			// printf("%lld\n", segTime.query(segTime.root[segTime.t], 1, inf, b, inf) % 2 == 0 ? A[i] : B[i]);
	}

	printf("%lld\n", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:68:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  int n, k; scanf("%lld %lld", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%lld %lld", A+i, B+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:74:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   int x; scanf("%lld", &x); X[i] = {x, i};
      |          ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct
3 Correct 4 ms 2248 KB Output is correct
4 Correct 4 ms 2360 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 4 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 4 ms 2252 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 4 ms 2244 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2292 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct
3 Correct 4 ms 2248 KB Output is correct
4 Correct 4 ms 2360 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 4 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 4 ms 2252 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 4 ms 2244 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2292 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 40 ms 20476 KB Output is correct
15 Correct 86 ms 40644 KB Output is correct
16 Correct 132 ms 60792 KB Output is correct
17 Correct 181 ms 80976 KB Output is correct
18 Correct 185 ms 80864 KB Output is correct
19 Correct 184 ms 81016 KB Output is correct
20 Correct 190 ms 80968 KB Output is correct
21 Correct 162 ms 81000 KB Output is correct
22 Correct 139 ms 80580 KB Output is correct
23 Correct 138 ms 80492 KB Output is correct
24 Correct 134 ms 80420 KB Output is correct
25 Correct 134 ms 80460 KB Output is correct
26 Correct 160 ms 80712 KB Output is correct
27 Correct 176 ms 80952 KB Output is correct
28 Correct 170 ms 80964 KB Output is correct
29 Correct 168 ms 80968 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct
3 Correct 4 ms 2248 KB Output is correct
4 Correct 4 ms 2360 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 4 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 4 ms 2252 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 4 ms 2244 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2292 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 40 ms 20476 KB Output is correct
15 Correct 86 ms 40644 KB Output is correct
16 Correct 132 ms 60792 KB Output is correct
17 Correct 181 ms 80976 KB Output is correct
18 Correct 185 ms 80864 KB Output is correct
19 Correct 184 ms 81016 KB Output is correct
20 Correct 190 ms 80968 KB Output is correct
21 Correct 162 ms 81000 KB Output is correct
22 Correct 139 ms 80580 KB Output is correct
23 Correct 138 ms 80492 KB Output is correct
24 Correct 134 ms 80420 KB Output is correct
25 Correct 134 ms 80460 KB Output is correct
26 Correct 160 ms 80712 KB Output is correct
27 Correct 176 ms 80952 KB Output is correct
28 Correct 170 ms 80964 KB Output is correct
29 Correct 168 ms 80968 KB Output is correct
30 Runtime error 418 ms 262148 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -