답안 #52238 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52238	2018-06-25T05:48:03 Z	윤교준(#1348)	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	2000 ms	78180 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[30 * 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	63 ms	70776 KB	Output is correct
2	Correct	62 ms	70884 KB	Output is correct
3	Correct	66 ms	70920 KB	Output is correct
4	Correct	69 ms	70920 KB	Output is correct
5	Correct	80 ms	70948 KB	Output is correct
6	Correct	68 ms	71040 KB	Output is correct
7	Correct	72 ms	71044 KB	Output is correct
8	Correct	61 ms	71044 KB	Output is correct
9	Correct	57 ms	71068 KB	Output is correct
10	Correct	58 ms	71072 KB	Output is correct
11	Correct	60 ms	71072 KB	Output is correct
12	Correct	59 ms	71072 KB	Output is correct
13	Correct	61 ms	71072 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	70776 KB	Output is correct
2	Correct	62 ms	70884 KB	Output is correct
3	Correct	66 ms	70920 KB	Output is correct
4	Correct	69 ms	70920 KB	Output is correct
5	Correct	80 ms	70948 KB	Output is correct
6	Correct	68 ms	71040 KB	Output is correct
7	Correct	72 ms	71044 KB	Output is correct
8	Correct	61 ms	71044 KB	Output is correct
9	Correct	57 ms	71068 KB	Output is correct
10	Correct	58 ms	71072 KB	Output is correct
11	Correct	60 ms	71072 KB	Output is correct
12	Correct	59 ms	71072 KB	Output is correct
13	Correct	61 ms	71072 KB	Output is correct
14	Correct	116 ms	71584 KB	Output is correct
15	Correct	231 ms	71992 KB	Output is correct
16	Correct	349 ms	72116 KB	Output is correct
17	Correct	438 ms	72492 KB	Output is correct
18	Correct	421 ms	72500 KB	Output is correct
19	Correct	511 ms	72612 KB	Output is correct
20	Correct	472 ms	72612 KB	Output is correct
21	Correct	386 ms	72612 KB	Output is correct
22	Correct	300 ms	72612 KB	Output is correct
23	Correct	304 ms	72612 KB	Output is correct
24	Correct	296 ms	72612 KB	Output is correct
25	Correct	292 ms	72612 KB	Output is correct
26	Correct	292 ms	72612 KB	Output is correct
27	Correct	384 ms	72612 KB	Output is correct
28	Correct	340 ms	72612 KB	Output is correct
29	Correct	287 ms	72612 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	70776 KB	Output is correct
2	Correct	62 ms	70884 KB	Output is correct
3	Correct	66 ms	70920 KB	Output is correct
4	Correct	69 ms	70920 KB	Output is correct
5	Correct	80 ms	70948 KB	Output is correct
6	Correct	68 ms	71040 KB	Output is correct
7	Correct	72 ms	71044 KB	Output is correct
8	Correct	61 ms	71044 KB	Output is correct
9	Correct	57 ms	71068 KB	Output is correct
10	Correct	58 ms	71072 KB	Output is correct
11	Correct	60 ms	71072 KB	Output is correct
12	Correct	59 ms	71072 KB	Output is correct
13	Correct	61 ms	71072 KB	Output is correct
14	Correct	116 ms	71584 KB	Output is correct
15	Correct	231 ms	71992 KB	Output is correct
16	Correct	349 ms	72116 KB	Output is correct
17	Correct	438 ms	72492 KB	Output is correct
18	Correct	421 ms	72500 KB	Output is correct
19	Correct	511 ms	72612 KB	Output is correct
20	Correct	472 ms	72612 KB	Output is correct
21	Correct	386 ms	72612 KB	Output is correct
22	Correct	300 ms	72612 KB	Output is correct
23	Correct	304 ms	72612 KB	Output is correct
24	Correct	296 ms	72612 KB	Output is correct
25	Correct	292 ms	72612 KB	Output is correct
26	Correct	292 ms	72612 KB	Output is correct
27	Correct	384 ms	72612 KB	Output is correct
28	Correct	340 ms	72612 KB	Output is correct
29	Correct	287 ms	72612 KB	Output is correct
30	Correct	416 ms	73688 KB	Output is correct
31	Correct	938 ms	74748 KB	Output is correct
32	Correct	1761 ms	75880 KB	Output is correct
33	Execution timed out	2066 ms	78180 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #52238

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