답안 #52244 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52244	2018-06-25T05:55:40 Z	윤교준(#1348)	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	963 ms	87332 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())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
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;
const int MX = 1048576;

struct SEG {
	int d[MX*2];

	void upd(int x, int r) {
		x += MX; upmax(d[x], r);
		for(x /= 2; x; x /= 2)
			d[x] = max(d[x*2], d[x*2+1]);
	}
	int get(int s, int e) {
		int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) upmax(r, d[s++]); if(~e&1) upmax(r, d[e--]);
		} return r;
	}
} seg;

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++) {
		seg.upd(CI[i], 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;
			}
			*/
			s = seg.get(mn, mx-1);
		}

		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:109:14: warning: unused variable 'e' [-Wunused-variable]
   int s = 0, e = K;
              ^
fortune_telling2.cpp:72: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	55 ms	70904 KB	Output is correct
2	Correct	55 ms	71140 KB	Output is correct
3	Correct	56 ms	71140 KB	Output is correct
4	Correct	57 ms	71140 KB	Output is correct
5	Correct	57 ms	71252 KB	Output is correct
6	Correct	64 ms	71252 KB	Output is correct
7	Correct	57 ms	71252 KB	Output is correct
8	Correct	55 ms	71252 KB	Output is correct
9	Correct	55 ms	71252 KB	Output is correct
10	Correct	63 ms	71252 KB	Output is correct
11	Correct	55 ms	71252 KB	Output is correct
12	Correct	55 ms	71252 KB	Output is correct
13	Correct	56 ms	71276 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	70904 KB	Output is correct
2	Correct	55 ms	71140 KB	Output is correct
3	Correct	56 ms	71140 KB	Output is correct
4	Correct	57 ms	71140 KB	Output is correct
5	Correct	57 ms	71252 KB	Output is correct
6	Correct	64 ms	71252 KB	Output is correct
7	Correct	57 ms	71252 KB	Output is correct
8	Correct	55 ms	71252 KB	Output is correct
9	Correct	55 ms	71252 KB	Output is correct
10	Correct	63 ms	71252 KB	Output is correct
11	Correct	55 ms	71252 KB	Output is correct
12	Correct	55 ms	71252 KB	Output is correct
13	Correct	56 ms	71276 KB	Output is correct
14	Correct	87 ms	72104 KB	Output is correct
15	Correct	100 ms	72824 KB	Output is correct
16	Correct	135 ms	73652 KB	Output is correct
17	Correct	170 ms	74424 KB	Output is correct
18	Correct	167 ms	74560 KB	Output is correct
19	Correct	169 ms	74560 KB	Output is correct
20	Correct	184 ms	74560 KB	Output is correct
21	Correct	153 ms	74560 KB	Output is correct
22	Correct	127 ms	74560 KB	Output is correct
23	Correct	136 ms	74560 KB	Output is correct
24	Correct	140 ms	74560 KB	Output is correct
25	Correct	166 ms	74560 KB	Output is correct
26	Correct	130 ms	74560 KB	Output is correct
27	Correct	155 ms	74560 KB	Output is correct
28	Correct	133 ms	74560 KB	Output is correct
29	Correct	165 ms	74560 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	55 ms	70904 KB	Output is correct
2	Correct	55 ms	71140 KB	Output is correct
3	Correct	56 ms	71140 KB	Output is correct
4	Correct	57 ms	71140 KB	Output is correct
5	Correct	57 ms	71252 KB	Output is correct
6	Correct	64 ms	71252 KB	Output is correct
7	Correct	57 ms	71252 KB	Output is correct
8	Correct	55 ms	71252 KB	Output is correct
9	Correct	55 ms	71252 KB	Output is correct
10	Correct	63 ms	71252 KB	Output is correct
11	Correct	55 ms	71252 KB	Output is correct
12	Correct	55 ms	71252 KB	Output is correct
13	Correct	56 ms	71276 KB	Output is correct
14	Correct	87 ms	72104 KB	Output is correct
15	Correct	100 ms	72824 KB	Output is correct
16	Correct	135 ms	73652 KB	Output is correct
17	Correct	170 ms	74424 KB	Output is correct
18	Correct	167 ms	74560 KB	Output is correct
19	Correct	169 ms	74560 KB	Output is correct
20	Correct	184 ms	74560 KB	Output is correct
21	Correct	153 ms	74560 KB	Output is correct
22	Correct	127 ms	74560 KB	Output is correct
23	Correct	136 ms	74560 KB	Output is correct
24	Correct	140 ms	74560 KB	Output is correct
25	Correct	166 ms	74560 KB	Output is correct
26	Correct	130 ms	74560 KB	Output is correct
27	Correct	155 ms	74560 KB	Output is correct
28	Correct	133 ms	74560 KB	Output is correct
29	Correct	165 ms	74560 KB	Output is correct
30	Correct	267 ms	77700 KB	Output is correct
31	Correct	386 ms	79664 KB	Output is correct
32	Correct	514 ms	82108 KB	Output is correct
33	Correct	912 ms	87296 KB	Output is correct
34	Correct	246 ms	87296 KB	Output is correct
35	Correct	899 ms	87296 KB	Output is correct
36	Correct	963 ms	87332 KB	Output is correct
37	Correct	864 ms	87332 KB	Output is correct
38	Correct	842 ms	87332 KB	Output is correct
39	Correct	808 ms	87332 KB	Output is correct
40	Correct	736 ms	87332 KB	Output is correct
41	Correct	825 ms	87332 KB	Output is correct
42	Correct	817 ms	87332 KB	Output is correct
43	Correct	401 ms	87332 KB	Output is correct
44	Correct	380 ms	87332 KB	Output is correct
45	Correct	398 ms	87332 KB	Output is correct
46	Correct	558 ms	87332 KB	Output is correct
47	Correct	473 ms	87332 KB	Output is correct
48	Correct	615 ms	87332 KB	Output is correct
49	Correct	599 ms	87332 KB	Output is correct

답안 #52244

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