답안 #52236 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52236	2018-06-25T05:45:28 Z	윤교준(#1348)	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	438 ms	100044 KB

fortune_telling2

#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef long long ll;

const int MAXN = 200005;
const int MAXK = 200005;
const int MAXX = 600005;

struct NOD {
	NOD() : l(0), r(0), dt(0) {}
	int l, r, dt;
};
NOD nod[20 * MAXK]; int nodc = 1;

int pst[MAXK];

int A[MAXN], B[MAXN], AI[MAXN], BI[MAXN];
int C[MAXK], CI[MAXK];

ll Ans;
int N, K;

void upd(int bi, int i, int s, int e, int x) {
	nod[i].dt = nod[bi].dt + 1;
	if(s == e) return;

	int m = (s+e) / 2;
	if(x <= m) {
		nod[i].l = nodc++;
		nod[i].r = nod[bi].r;
		upd(nod[bi].l, nod[i].l, s, m, x);
	} else {
		nod[i].r = nodc++;
		nod[i].l = nod[bi].l;
		upd(nod[bi].r, nod[i].r, m+1, e, x);
	}
}

int get(int i, int s, int e, int p, int q) {
	if(!nod[i].dt || q < p || e < p || q < s) return 0;
	if(p <= s && e <= q) return nod[i].dt;
	int m = (s+e) / 2;
	return get(nod[i].l, s, m, p, q) + get(nod[i].r, m+1, e, p, q);
}

int main() {
	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++) scanf("%d", &C[i]);

	{
		vector<int> V;
		for(int i = 1; i <= N; i++) {
			V.pb(A[i]);
			V.pb(B[i]);
		}
		for(int i = 1; i <= K; i++) V.pb(C[i]);

		sorv(V); univ(V);

		for(int i = 1; i <= N; i++) {
			AI[i] = (int)(lower_bound(allv(V), A[i]) - V.begin());
			BI[i] = (int)(lower_bound(allv(V), B[i]) - V.begin());
		}
		for(int i = 1; i <= K; i++) {
			CI[i] = (int)(lower_bound(allv(V), C[i]) - V.begin());
		}

		V.clear();
	}

	for(int i = 1; i <= K; i++) {
		pst[i] = nodc++;
		upd(pst[i-1], pst[i], 0, MAXX, CI[i]);
	}

	for(int i = 1; i <= N; i++) {
		int mn, mx; tie(mn, mx) = minmax(AI[i], BI[i]);

		int totcnt = get(pst[K], 0, MAXX, mn, mx-1);
		int s = 0, e = K;

		if(!totcnt) {
			totcnt = get(pst[K], 0, MAXX, mx, MAXX);
			Ans += (totcnt & 1) ? B[i] : A[i];
			continue;
		} else {
			for(int m, c; s < e;) {
				m = (s+e)/2;
				c = get(pst[m], 0, MAXX, mn, mx-1);
				if(c < totcnt) s = m+1;
				else e = m;
			}
		}

		totcnt = get(pst[K], 0, MAXX, mx, MAXX) - get(pst[s], 0, MAXX, mx, MAXX);

		if(A[i] < B[i])
			Ans += (totcnt & 1) ? A[i] : B[i];
		else
			Ans += (totcnt & 1) ? B[i] : A[i];
	}

	printf("%lld\n", Ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:52: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:53:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d%d", &A[i], &B[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:54:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= K; i++) scanf("%d", &C[i]);
                              ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	47352 KB	Output is correct
2	Correct	40 ms	47352 KB	Output is correct
3	Correct	42 ms	47368 KB	Output is correct
4	Correct	51 ms	47412 KB	Output is correct
5	Correct	50 ms	47428 KB	Output is correct
6	Correct	42 ms	47444 KB	Output is correct
7	Correct	42 ms	47444 KB	Output is correct
8	Correct	41 ms	47444 KB	Output is correct
9	Correct	40 ms	47460 KB	Output is correct
10	Correct	41 ms	47472 KB	Output is correct
11	Correct	45 ms	47472 KB	Output is correct
12	Correct	41 ms	47472 KB	Output is correct
13	Correct	42 ms	47472 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	47352 KB	Output is correct
2	Correct	40 ms	47352 KB	Output is correct
3	Correct	42 ms	47368 KB	Output is correct
4	Correct	51 ms	47412 KB	Output is correct
5	Correct	50 ms	47428 KB	Output is correct
6	Correct	42 ms	47444 KB	Output is correct
7	Correct	42 ms	47444 KB	Output is correct
8	Correct	41 ms	47444 KB	Output is correct
9	Correct	40 ms	47460 KB	Output is correct
10	Correct	41 ms	47472 KB	Output is correct
11	Correct	45 ms	47472 KB	Output is correct
12	Correct	41 ms	47472 KB	Output is correct
13	Correct	42 ms	47472 KB	Output is correct
14	Correct	111 ms	47924 KB	Output is correct
15	Correct	183 ms	48332 KB	Output is correct
16	Correct	277 ms	48648 KB	Output is correct
17	Correct	388 ms	49060 KB	Output is correct
18	Correct	388 ms	49188 KB	Output is correct
19	Correct	392 ms	49188 KB	Output is correct
20	Correct	438 ms	49188 KB	Output is correct
21	Correct	356 ms	49188 KB	Output is correct
22	Correct	287 ms	49188 KB	Output is correct
23	Correct	358 ms	49188 KB	Output is correct
24	Correct	380 ms	49188 KB	Output is correct
25	Correct	298 ms	49188 KB	Output is correct
26	Correct	288 ms	49188 KB	Output is correct
27	Correct	306 ms	49188 KB	Output is correct
28	Correct	274 ms	49188 KB	Output is correct
29	Correct	207 ms	49256 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	47352 KB	Output is correct
2	Correct	40 ms	47352 KB	Output is correct
3	Correct	42 ms	47368 KB	Output is correct
4	Correct	51 ms	47412 KB	Output is correct
5	Correct	50 ms	47428 KB	Output is correct
6	Correct	42 ms	47444 KB	Output is correct
7	Correct	42 ms	47444 KB	Output is correct
8	Correct	41 ms	47444 KB	Output is correct
9	Correct	40 ms	47460 KB	Output is correct
10	Correct	41 ms	47472 KB	Output is correct
11	Correct	45 ms	47472 KB	Output is correct
12	Correct	41 ms	47472 KB	Output is correct
13	Correct	42 ms	47472 KB	Output is correct
14	Correct	111 ms	47924 KB	Output is correct
15	Correct	183 ms	48332 KB	Output is correct
16	Correct	277 ms	48648 KB	Output is correct
17	Correct	388 ms	49060 KB	Output is correct
18	Correct	388 ms	49188 KB	Output is correct
19	Correct	392 ms	49188 KB	Output is correct
20	Correct	438 ms	49188 KB	Output is correct
21	Correct	356 ms	49188 KB	Output is correct
22	Correct	287 ms	49188 KB	Output is correct
23	Correct	358 ms	49188 KB	Output is correct
24	Correct	380 ms	49188 KB	Output is correct
25	Correct	298 ms	49188 KB	Output is correct
26	Correct	288 ms	49188 KB	Output is correct
27	Correct	306 ms	49188 KB	Output is correct
28	Correct	274 ms	49188 KB	Output is correct
29	Correct	207 ms	49256 KB	Output is correct
30	Runtime error	274 ms	100044 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #52236

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
0 / 65.0