답안 #52239 :: oj.uz

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

fortune_telling2

#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#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;
static unsigned char str[55000055], *p = str;

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() {
	fread(str, 1, 55000055, stdin);
	rf(N) rf(K)
	for(int i = 1; i <= N; i++) { rf(A[i]) rf(B[i]) }
	for(int i = 1; i <= K; i++) { rf(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:54:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 55000055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	70904 KB	Output is correct
2	Correct	59 ms	70904 KB	Output is correct
3	Correct	61 ms	70940 KB	Output is correct
4	Correct	60 ms	70940 KB	Output is correct
5	Correct	66 ms	70988 KB	Output is correct
6	Correct	70 ms	71020 KB	Output is correct
7	Correct	70 ms	71148 KB	Output is correct
8	Correct	61 ms	71148 KB	Output is correct
9	Correct	60 ms	71148 KB	Output is correct
10	Correct	71 ms	71148 KB	Output is correct
11	Correct	61 ms	71148 KB	Output is correct
12	Correct	71 ms	71148 KB	Output is correct
13	Correct	72 ms	71148 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	70904 KB	Output is correct
2	Correct	59 ms	70904 KB	Output is correct
3	Correct	61 ms	70940 KB	Output is correct
4	Correct	60 ms	70940 KB	Output is correct
5	Correct	66 ms	70988 KB	Output is correct
6	Correct	70 ms	71020 KB	Output is correct
7	Correct	70 ms	71148 KB	Output is correct
8	Correct	61 ms	71148 KB	Output is correct
9	Correct	60 ms	71148 KB	Output is correct
10	Correct	71 ms	71148 KB	Output is correct
11	Correct	61 ms	71148 KB	Output is correct
12	Correct	71 ms	71148 KB	Output is correct
13	Correct	72 ms	71148 KB	Output is correct
14	Correct	162 ms	71828 KB	Output is correct
15	Correct	197 ms	72384 KB	Output is correct
16	Correct	315 ms	72976 KB	Output is correct
17	Correct	463 ms	73612 KB	Output is correct
18	Correct	399 ms	73620 KB	Output is correct
19	Correct	394 ms	73748 KB	Output is correct
20	Correct	407 ms	73748 KB	Output is correct
21	Correct	373 ms	73780 KB	Output is correct
22	Correct	330 ms	73780 KB	Output is correct
23	Correct	297 ms	73780 KB	Output is correct
24	Correct	291 ms	73780 KB	Output is correct
25	Correct	283 ms	73780 KB	Output is correct
26	Correct	267 ms	73780 KB	Output is correct
27	Correct	322 ms	73780 KB	Output is correct
28	Correct	289 ms	73844 KB	Output is correct
29	Correct	216 ms	73844 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	70904 KB	Output is correct
2	Correct	59 ms	70904 KB	Output is correct
3	Correct	61 ms	70940 KB	Output is correct
4	Correct	60 ms	70940 KB	Output is correct
5	Correct	66 ms	70988 KB	Output is correct
6	Correct	70 ms	71020 KB	Output is correct
7	Correct	70 ms	71148 KB	Output is correct
8	Correct	61 ms	71148 KB	Output is correct
9	Correct	60 ms	71148 KB	Output is correct
10	Correct	71 ms	71148 KB	Output is correct
11	Correct	61 ms	71148 KB	Output is correct
12	Correct	71 ms	71148 KB	Output is correct
13	Correct	72 ms	71148 KB	Output is correct
14	Correct	162 ms	71828 KB	Output is correct
15	Correct	197 ms	72384 KB	Output is correct
16	Correct	315 ms	72976 KB	Output is correct
17	Correct	463 ms	73612 KB	Output is correct
18	Correct	399 ms	73620 KB	Output is correct
19	Correct	394 ms	73748 KB	Output is correct
20	Correct	407 ms	73748 KB	Output is correct
21	Correct	373 ms	73780 KB	Output is correct
22	Correct	330 ms	73780 KB	Output is correct
23	Correct	297 ms	73780 KB	Output is correct
24	Correct	291 ms	73780 KB	Output is correct
25	Correct	283 ms	73780 KB	Output is correct
26	Correct	267 ms	73780 KB	Output is correct
27	Correct	322 ms	73780 KB	Output is correct
28	Correct	289 ms	73844 KB	Output is correct
29	Correct	216 ms	73844 KB	Output is correct
30	Correct	344 ms	75872 KB	Output is correct
31	Correct	853 ms	77544 KB	Output is correct
32	Correct	1470 ms	79708 KB	Output is correct
33	Execution timed out	2068 ms	83996 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #52239

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