Submission #529529

#	Time	Username	Problem	Language	Result	Execution time	Memory
529529		LucaDantas	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	407 ms	262148 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65