Submission #52242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
52242	2018-06-25T05:52:57 Z	윤교준(#1348)	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	35 / 100	3000 ms	84024 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;
const int MX = 1048576;

struct SEG {
	int d[MX*2];

};

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:60: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	57 ms	70904 KB	Output is correct
2	Correct	57 ms	71024 KB	Output is correct
3	Correct	62 ms	71024 KB	Output is correct
4	Correct	59 ms	71024 KB	Output is correct
5	Correct	60 ms	71024 KB	Output is correct
6	Correct	64 ms	71024 KB	Output is correct
7	Correct	59 ms	71024 KB	Output is correct
8	Correct	61 ms	71044 KB	Output is correct
9	Correct	57 ms	71044 KB	Output is correct
10	Correct	59 ms	71080 KB	Output is correct
11	Correct	59 ms	71080 KB	Output is correct
12	Correct	58 ms	71144 KB	Output is correct
13	Correct	58 ms	71144 KB	Output is correct

Subtask #2
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	70904 KB	Output is correct
2	Correct	57 ms	71024 KB	Output is correct
3	Correct	62 ms	71024 KB	Output is correct
4	Correct	59 ms	71024 KB	Output is correct
5	Correct	60 ms	71024 KB	Output is correct
6	Correct	64 ms	71024 KB	Output is correct
7	Correct	59 ms	71024 KB	Output is correct
8	Correct	61 ms	71044 KB	Output is correct
9	Correct	57 ms	71044 KB	Output is correct
10	Correct	59 ms	71080 KB	Output is correct
11	Correct	59 ms	71080 KB	Output is correct
12	Correct	58 ms	71144 KB	Output is correct
13	Correct	58 ms	71144 KB	Output is correct
14	Correct	115 ms	71880 KB	Output is correct
15	Correct	203 ms	72444 KB	Output is correct
16	Correct	279 ms	73028 KB	Output is correct
17	Correct	485 ms	73668 KB	Output is correct
18	Correct	385 ms	73668 KB	Output is correct
19	Correct	398 ms	73796 KB	Output is correct
20	Correct	372 ms	73796 KB	Output is correct
21	Correct	347 ms	73796 KB	Output is correct
22	Correct	283 ms	73796 KB	Output is correct
23	Correct	287 ms	73796 KB	Output is correct
24	Correct	297 ms	73796 KB	Output is correct
25	Correct	280 ms	73796 KB	Output is correct
26	Correct	284 ms	73796 KB	Output is correct
27	Correct	322 ms	73796 KB	Output is correct
28	Correct	268 ms	73924 KB	Output is correct
29	Correct	198 ms	73924 KB	Output is correct

Subtask #3
0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	70904 KB	Output is correct
2	Correct	57 ms	71024 KB	Output is correct
3	Correct	62 ms	71024 KB	Output is correct
4	Correct	59 ms	71024 KB	Output is correct
5	Correct	60 ms	71024 KB	Output is correct
6	Correct	64 ms	71024 KB	Output is correct
7	Correct	59 ms	71024 KB	Output is correct
8	Correct	61 ms	71044 KB	Output is correct
9	Correct	57 ms	71044 KB	Output is correct
10	Correct	59 ms	71080 KB	Output is correct
11	Correct	59 ms	71080 KB	Output is correct
12	Correct	58 ms	71144 KB	Output is correct
13	Correct	58 ms	71144 KB	Output is correct
14	Correct	115 ms	71880 KB	Output is correct
15	Correct	203 ms	72444 KB	Output is correct
16	Correct	279 ms	73028 KB	Output is correct
17	Correct	485 ms	73668 KB	Output is correct
18	Correct	385 ms	73668 KB	Output is correct
19	Correct	398 ms	73796 KB	Output is correct
20	Correct	372 ms	73796 KB	Output is correct
21	Correct	347 ms	73796 KB	Output is correct
22	Correct	283 ms	73796 KB	Output is correct
23	Correct	287 ms	73796 KB	Output is correct
24	Correct	297 ms	73796 KB	Output is correct
25	Correct	280 ms	73796 KB	Output is correct
26	Correct	284 ms	73796 KB	Output is correct
27	Correct	322 ms	73796 KB	Output is correct
28	Correct	268 ms	73924 KB	Output is correct
29	Correct	198 ms	73924 KB	Output is correct
30	Correct	364 ms	75860 KB	Output is correct
31	Correct	932 ms	77556 KB	Output is correct
32	Correct	1620 ms	79796 KB	Output is correct
33	Correct	2982 ms	84024 KB	Output is correct
34	Correct	232 ms	84024 KB	Output is correct
35	Execution timed out	3033 ms	84024 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Submission #52242

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