Submission #112171

#	Time	Username	Problem	Language	Result	Execution time	Memory
112171		kimjg1119	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	556 ms	110352 KiB

fortune_telling2

#define _CRT_SECURE_NO_WARNINGS

#include <algorithm>
#include <cstdio>
#include <vector>
#include <functional>
#define x first
#define y second


using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
typedef long long ll;

typedef struct node {
	int le, ri;
	int val;
}node;

typedef struct SegmentTree {
	vector<node> N;
	int root, n;
	int alloc() {
		N.push_back({ -1,-1,0 });
		return (int)N.size()-1;
	}
	SegmentTree(int _n) : n(_n) {
		root = alloc();
	}
	void update(int nx, int st, int en, int idx, int val) {
		if (st == en && idx == st) {
			N[nx].val = max(N[nx].val, val);
			return;
		}
		else if (idx < st || en < idx) return;
		int mid = ((ll)st + (ll)en) / 2;
		if (N[nx].le == -1) {
			int t = alloc();
			N[nx].le = t;
		}
		if (N[nx].ri == -1) {
			int t = alloc();
			N[nx].ri = t;
		}
		update(N[nx].le, st, mid, idx, val);
		update(N[nx].ri, mid + 1, en, idx, val);
		N[nx].val = max(N[N[nx].le].val, N[N[nx].ri].val);
	}
	void update(int idx, int val) {
		return update(root, 0, n - 1, idx, val);
	}
	int query(int nx, int st, int en, int le, int ri) {
		if (nx == -1) return 0;
		if (le <= st && en <= ri) return N[nx].val;
		else if (ri < st || en < le) return 0;
		int mid = ((ll)st + (ll)en) / 2;
		return max(query(N[nx].le, st, mid, le, ri), query(N[nx].ri, mid + 1, en, le, ri));
	}
	int query(int le, int ri) {
		return query(root, 0, n - 1, le, ri);
	}
}ST;

int tree[200005];
void update(int idx) {
	for (int i = idx; i < 200005; i += (i&-i))
		tree[i] += 1;
}
int query(int idx) {
	int s = 0;
	for (int i = idx; i > 0; i -= (i&-i))
		s += tree[i];
	return s;
}

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	vector<pii> V, Q;
	for (int i = 0; i < n; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		V.emplace_back(t1, t2);
	}
	sort(V.begin(), V.end(), [&](pii a, pii b) {
		return min(a.x, a.y) > min(b.x, b.y);
	});
	for (int i = 0; i < k; i++) {
		int t;
		scanf("%d", &t);
		Q.emplace_back(t, i+1);
	}
	sort(Q.begin(), Q.end(), greater<pii>());

	int last = 0;
	ll ans = 0;
	ST S(2 * 1e9 + 5);
	for (int i = 0; i < V.size(); i++) {
		int a = min(V[i].x, V[i].y), b = max(V[i].x, V[i].y);
		while (last < Q.size()) {
			if (Q[last].x >= a) {
				S.update(Q[last].x, Q[last].y);
				update(Q[last].y);
				last++;
			}
			else break;
		}
		int bound = S.query(a, b - 1);
		if (!bound) {
			if (last % 2) ans += V[i].y;
			else ans += V[i].x;
			continue;
		}
		int ret = query(200000) - query(bound);
		if (ret % 2) ans += a;
		else ans += b;
	}
	printf("%lld", ans);
	return 0;
}

/*
1. a를 하나 받아온다
2. a까지의 질의들을 모두 처리함
2-1. 몇번째 쿼리인지를 기록해둬야겠다
2-2. 그러니까 쿼리의 높이와 순서를 같이 기록해 두고 높이순으로 정렬해 둬야 한다는 말이지.
3. a 이상 b 미만인 애들 중 가장 나중에 나오는 질의를 찾고, 그 질의 이후에 나오는 P 개수를 세야함
3-1. 각 높이에 질의 number을 업데이트 해줘야할거같다
3-2. 그러면 높이 범위에서 가장 나중에 나오는 질의 번호를 찾을 수 있을거고
3-3. 그 질의 번호 이후에 나오는 질의 개수를 펜윅으로 구해줄 수 있을거다
4. 그 개수만큼 뒤집어
*/

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
fortune_telling2.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (last < Q.size()) {
          ~~~~~^~~~~~~~~~
fortune_telling2.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t1, &t2);
   ~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65