답안 #52173 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52173	2018-06-24T13:09:00 Z	ainta	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	412 ms	130632 KB

fortune_telling2

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 524288
using namespace std;
int n, K;
struct point {
	int a, b;
}w[201000], ori[201000];
int X[401000], P[201000], Q[201000], IT[SZ+SZ];
vector<int>G[401000];
int BIT[SZ];
void Ins(int a, int b) {
	a += SZ;
	while (a) {
		IT[a] = max(IT[a], b);
		a >>= 1;
	}
}
void Add(int a, int b) {
	while (a < SZ) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}
int Max(int b, int e) {
	b += SZ, e += SZ;
	int r = 0;
	while (b <= e) {
		r = max(r, max(IT[b], IT[e]));
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
long long res;
int main() {
	int i, a;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i].a, &w[i].b);
		X[i] = w[i].a, X[n + i] = w[i].b;
		ori[i] = w[i];
	}
	sort(X + 1, X + n + n + 1);
	for (i = 1; i <= n; i++) {
		w[i].a = lower_bound(X + 1, X + n + n + 1, w[i].a) - X;
		w[i].b = lower_bound(X + 1, X + n + n + 1, w[i].b) - X;
	}
	for (i = 1; i <= K; i++) {
		scanf("%d", &a);
		a = lower_bound(X + 1, X + n + n + 1, a + 1) - X;
		Q[i] = a;
		Ins(a, i);
	}
	for (i = 1; i <= n; i++) {
		int mn = min(w[i].a, w[i].b), mx = max(w[i].a, w[i].b);
		G[Max(mn+1,mx)].push_back(i);
	}
	for (i = K; i >= 0; i--) {
		for (auto &x : G[i]) {
			int ck = ((K - i) - Sum(w[x].b)) % 2;
			if (i) {
				if (ck)res += min(ori[x].a, ori[x].b);
				else res += max(ori[x].a, ori[x].b);
			}
			else {
				if (ck)res += ori[x].b;
				else res += ori[x].a;
			}
		}
		if (!i)break;
		Add(Q[i], 1);
	}
	printf("%lld\n", res);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:46: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].a, &w[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9848 KB	Output is correct
2	Correct	11 ms	10012 KB	Output is correct
3	Correct	11 ms	10012 KB	Output is correct
4	Correct	11 ms	10016 KB	Output is correct
5	Correct	11 ms	10016 KB	Output is correct
6	Correct	11 ms	10016 KB	Output is correct
7	Correct	11 ms	10016 KB	Output is correct
8	Correct	12 ms	10016 KB	Output is correct
9	Correct	11 ms	10016 KB	Output is correct
10	Correct	12 ms	10016 KB	Output is correct
11	Correct	11 ms	10016 KB	Output is correct
12	Correct	11 ms	10120 KB	Output is correct
13	Correct	11 ms	10120 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9848 KB	Output is correct
2	Correct	11 ms	10012 KB	Output is correct
3	Correct	11 ms	10012 KB	Output is correct
4	Correct	11 ms	10016 KB	Output is correct
5	Correct	11 ms	10016 KB	Output is correct
6	Correct	11 ms	10016 KB	Output is correct
7	Correct	11 ms	10016 KB	Output is correct
8	Correct	12 ms	10016 KB	Output is correct
9	Correct	11 ms	10016 KB	Output is correct
10	Correct	12 ms	10016 KB	Output is correct
11	Correct	11 ms	10016 KB	Output is correct
12	Correct	11 ms	10120 KB	Output is correct
13	Correct	11 ms	10120 KB	Output is correct
14	Correct	25 ms	10524 KB	Output is correct
15	Correct	39 ms	11160 KB	Output is correct
16	Correct	56 ms	12568 KB	Output is correct
17	Correct	70 ms	14276 KB	Output is correct
18	Correct	74 ms	15456 KB	Output is correct
19	Correct	84 ms	16604 KB	Output is correct
20	Correct	71 ms	17924 KB	Output is correct
21	Correct	65 ms	18936 KB	Output is correct
22	Correct	49 ms	19564 KB	Output is correct
23	Correct	51 ms	20460 KB	Output is correct
24	Correct	53 ms	20904 KB	Output is correct
25	Correct	47 ms	21740 KB	Output is correct
26	Correct	51 ms	22188 KB	Output is correct
27	Correct	61 ms	23804 KB	Output is correct
28	Correct	57 ms	24492 KB	Output is correct
29	Correct	65 ms	26160 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9848 KB	Output is correct
2	Correct	11 ms	10012 KB	Output is correct
3	Correct	11 ms	10012 KB	Output is correct
4	Correct	11 ms	10016 KB	Output is correct
5	Correct	11 ms	10016 KB	Output is correct
6	Correct	11 ms	10016 KB	Output is correct
7	Correct	11 ms	10016 KB	Output is correct
8	Correct	12 ms	10016 KB	Output is correct
9	Correct	11 ms	10016 KB	Output is correct
10	Correct	12 ms	10016 KB	Output is correct
11	Correct	11 ms	10016 KB	Output is correct
12	Correct	11 ms	10120 KB	Output is correct
13	Correct	11 ms	10120 KB	Output is correct
14	Correct	25 ms	10524 KB	Output is correct
15	Correct	39 ms	11160 KB	Output is correct
16	Correct	56 ms	12568 KB	Output is correct
17	Correct	70 ms	14276 KB	Output is correct
18	Correct	74 ms	15456 KB	Output is correct
19	Correct	84 ms	16604 KB	Output is correct
20	Correct	71 ms	17924 KB	Output is correct
21	Correct	65 ms	18936 KB	Output is correct
22	Correct	49 ms	19564 KB	Output is correct
23	Correct	51 ms	20460 KB	Output is correct
24	Correct	53 ms	20904 KB	Output is correct
25	Correct	47 ms	21740 KB	Output is correct
26	Correct	51 ms	22188 KB	Output is correct
27	Correct	61 ms	23804 KB	Output is correct
28	Correct	57 ms	24492 KB	Output is correct
29	Correct	65 ms	26160 KB	Output is correct
30	Correct	95 ms	27360 KB	Output is correct
31	Correct	158 ms	32360 KB	Output is correct
32	Correct	235 ms	38868 KB	Output is correct
33	Correct	379 ms	49792 KB	Output is correct
34	Correct	77 ms	49792 KB	Output is correct
35	Correct	395 ms	57620 KB	Output is correct
36	Correct	386 ms	63296 KB	Output is correct
37	Correct	412 ms	69344 KB	Output is correct
38	Correct	379 ms	75104 KB	Output is correct
39	Correct	376 ms	80992 KB	Output is correct
40	Correct	357 ms	86528 KB	Output is correct
41	Correct	380 ms	92308 KB	Output is correct
42	Correct	385 ms	98144 KB	Output is correct
43	Correct	170 ms	100468 KB	Output is correct
44	Correct	170 ms	106064 KB	Output is correct
45	Correct	170 ms	112548 KB	Output is correct
46	Correct	248 ms	117404 KB	Output is correct
47	Correct	261 ms	121212 KB	Output is correct
48	Correct	276 ms	125096 KB	Output is correct
49	Correct	276 ms	130632 KB	Output is correct

답안 #52173

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0