oj.uz

Submission #52244

# Submission time Handle Problem Language Result Execution time Memory
52244 2018-06-25T05:55:40 Z 윤교준(#1348) Fortune Telling 2 (JOI14_fortune_telling2) C++11
100 / 100
 963 ms 87332 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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