oj.uz

Submission #529529

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

constexpr int maxn = 2e5+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("%d %d\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];

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

	for(int i = 1; i <= k; i++) {
		int x; scanf("%d", &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, 0)) - X) - 1;
			int itR = (lower_bound(X+1, X+1+k, pair<int,int>(b, 0)) - X) - 1;
			
			// printf("%d %d -> %d %d\n", a, b, itL, itR);
			last = segX.last(segX.root[itL], segX.root[itR], 1, inf);
		} else last = 0;

		/* printf("%d %d -> %d %d %d\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("%d\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("%d\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 'int main()':
fortune_telling2.cpp:66:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d %d", A+i, B+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:72:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   int x; scanf("%d", &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 2252 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 3 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 2252 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2252 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 2252 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 3 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 2252 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2252 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 40 ms 20020 KB Output is correct
15 Correct 83 ms 39684 KB Output is correct
16 Correct 136 ms 59352 KB Output is correct
17 Correct 179 ms 79176 KB Output is correct
18 Correct 185 ms 79148 KB Output is correct
19 Correct 177 ms 79172 KB Output is correct
20 Correct 184 ms 79084 KB Output is correct
21 Correct 166 ms 79160 KB Output is correct
22 Correct 131 ms 79100 KB Output is correct
23 Correct 133 ms 79140 KB Output is correct
24 Correct 134 ms 79124 KB Output is correct
25 Correct 134 ms 79256 KB Output is correct
26 Correct 153 ms 79020 KB Output is correct
27 Correct 176 ms 79172 KB Output is correct
28 Correct 158 ms 79112 KB Output is correct
29 Correct 169 ms 79172 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 2252 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 3 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 2252 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 4 ms 2252 KB Output is correct
13 Correct 4 ms 2252 KB Output is correct
14 Correct 40 ms 20020 KB Output is correct
15 Correct 83 ms 39684 KB Output is correct
16 Correct 136 ms 59352 KB Output is correct
17 Correct 179 ms 79176 KB Output is correct
18 Correct 185 ms 79148 KB Output is correct
19 Correct 177 ms 79172 KB Output is correct
20 Correct 184 ms 79084 KB Output is correct
21 Correct 166 ms 79160 KB Output is correct
22 Correct 131 ms 79100 KB Output is correct
23 Correct 133 ms 79140 KB Output is correct
24 Correct 134 ms 79124 KB Output is correct
25 Correct 134 ms 79256 KB Output is correct
26 Correct 153 ms 79020 KB Output is correct
27 Correct 176 ms 79172 KB Output is correct
28 Correct 158 ms 79112 KB Output is correct
29 Correct 169 ms 79172 KB Output is correct
30 Runtime error 407 ms 262148 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -