oj.uz

Submission #112171

# Submission time Handle Problem Language Result Execution time Memory
112171 2019-05-17T17:07:38 Z kimjg1119 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 556 ms 110352 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 21 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct
12 Correct 4 ms 1280 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 21 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct
12 Correct 4 ms 1280 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 22 ms 7144 KB Output is correct
15 Correct 51 ms 13708 KB Output is correct
16 Correct 69 ms 14300 KB Output is correct
17 Correct 101 ms 27432 KB Output is correct
18 Correct 100 ms 27360 KB Output is correct
19 Correct 94 ms 27384 KB Output is correct
20 Correct 88 ms 27464 KB Output is correct
21 Correct 93 ms 27336 KB Output is correct
22 Correct 46 ms 3792 KB Output is correct
23 Correct 46 ms 3792 KB Output is correct
24 Correct 45 ms 3800 KB Output is correct
25 Correct 48 ms 5372 KB Output is correct
26 Correct 78 ms 27220 KB Output is correct
27 Correct 77 ms 27336 KB Output is correct
28 Correct 85 ms 27292 KB Output is correct
29 Correct 78 ms 27340 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 21 ms 1280 KB Output is correct
5 Correct 4 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct
12 Correct 4 ms 1280 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 22 ms 7144 KB Output is correct
15 Correct 51 ms 13708 KB Output is correct
16 Correct 69 ms 14300 KB Output is correct
17 Correct 101 ms 27432 KB Output is correct
18 Correct 100 ms 27360 KB Output is correct
19 Correct 94 ms 27384 KB Output is correct
20 Correct 88 ms 27464 KB Output is correct
21 Correct 93 ms 27336 KB Output is correct
22 Correct 46 ms 3792 KB Output is correct
23 Correct 46 ms 3792 KB Output is correct
24 Correct 45 ms 3800 KB Output is correct
25 Correct 48 ms 5372 KB Output is correct
26 Correct 78 ms 27220 KB Output is correct
27 Correct 77 ms 27336 KB Output is correct
28 Correct 85 ms 27292 KB Output is correct
29 Correct 78 ms 27340 KB Output is correct
30 Correct 269 ms 105232 KB Output is correct
31 Correct 330 ms 106044 KB Output is correct
32 Correct 385 ms 107520 KB Output is correct
33 Correct 514 ms 110232 KB Output is correct
34 Correct 248 ms 104696 KB Output is correct
35 Correct 515 ms 110324 KB Output is correct
36 Correct 512 ms 110064 KB Output is correct
37 Correct 556 ms 110072 KB Output is correct
38 Correct 495 ms 110288 KB Output is correct
39 Correct 453 ms 110072 KB Output is correct
40 Correct 430 ms 109956 KB Output is correct
41 Correct 415 ms 110068 KB Output is correct
42 Correct 430 ms 110112 KB Output is correct
43 Correct 353 ms 109432 KB Output is correct
44 Correct 355 ms 109544 KB Output is correct
45 Correct 305 ms 60156 KB Output is correct
46 Correct 249 ms 15932 KB Output is correct
47 Correct 224 ms 15704 KB Output is correct
48 Correct 401 ms 110352 KB Output is correct
49 Correct 456 ms 110156 KB Output is correct