답안 #59225 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59225	2018-07-21T09:10:04 Z	gusfring	운세 보기 2 (JOI14_fortune_telling2)	C++14	35 / 100	766 ms	121340 KB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

const int MAXN = 2e5 + 5;

int twopow[20] = {0};
int mypow(int x, int e) {
	if (twopow[e]) return twopow[e];
	if (e == 0) return 1;
	int a = mypow(x, e/2);
	return (twopow[e] = (e % 2 == 0) ? a*a : a*a*x);
}

int N, K;
vii cisimler;
map<int, int> tbl;
map<int, int> revtbl;
int queries[MAXN];
vii qs;
int rmqtbl[MAXN][18];
int rminqtbl[MAXN][18];
vii tickets;
bool kucuk[MAXN];
 
int rmq(int a, int b) {
	int pop = b - a + 1;
	int e = (int)log2(pop);
	int a2 = b - mypow(2, e) + 1;
	return max(rmqtbl[a][e], rmqtbl[a2][e]);
}
int rminq(int a, int b) {
	int pop = b - a + 1;
	int e = (int)log2(pop);
	int a2 = b - mypow(2, e) + 1;
	return min(rminqtbl[a][e], rminqtbl[a2][e]);
}
int binsrc(int x) {
	int l = 0, r = K;
	while (r > l) {
		int mid = (l + r) / 2;
		if (qs[mid].first >= x) r = mid;
		else l = mid+1;
	}
	return l;
}
 
int bit[524289] = {0};
void bitinc(int x) {
	x += 2;
	while (x <= 524288) {
		bit[x]++;
		x += x & -x;
	}
}
int bitget(int x) {
	x += 2;
	int sum = 0;
	while (x > 0) {
		sum += bit[x];
		x -= x & -x;
	}
	return sum;
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> N >> K;
	set<int> S;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		cisimler.pb(mp(a, b));
		S.insert(a);
		S.insert(b);
	}
	for (int i = 0; i < K; i++) {
		int a; cin >> a;
		queries[i] = a;
		qs.pb(mp(a, i));
		S.insert(a);
	}
	int c = 0;
	while ( ! S.empty() ) {
		int x = *S.begin();
		S.erase(S.begin());
		tbl[x] = c;
		revtbl[c] = x;
		c++;
	}
	for (int i = 0; i < N; i++) {
		cisimler[i].first = tbl[cisimler[i].first];
		cisimler[i].second = tbl[cisimler[i].second];
	}
	for (int i = 0; i < K; i++) {
		queries[i] = tbl[queries[i]];
		qs[i].first = tbl[qs[i].first];
	}
	sort(qs.begin(), qs.end());
	for (int i = 0; i < K; i++) {
		rmqtbl[i][0] = qs[i].second;
		rminqtbl[i][0] = qs[i].second;
	}
	for (int e = 1; e < 18; e++) {
		int off = mypow(2, e-1);
		for (int i = 0; i < K; i++) {
			rmqtbl[i][e] = max(rmqtbl[i][e-1], rmqtbl[i+off][e-1]);
			rminqtbl[i][e] = min(rminqtbl[i][e-1], rminqtbl[i+off][e-1]);
		}
	}
	for (int i = 0; i < N; i++) {
		int cmin = min(cisimler[i].first, cisimler[i].second);
		int cmax = max(cisimler[i].first, cisimler[i].second);
		int ls = binsrc(cmin);
		int hs = binsrc(cmax);
		if (ls == K) {
			kucuk[i] = (cmin == cisimler[i].first);
			continue;
		} 
		if (hs == K) {
			kucuk[i] = false;
			continue;
		}
		if (ls != hs) {
			int q = rmq(ls, hs-1);
			tickets.pb(mp(q+1, i));
		}
	 	else {
			int q = rminq(ls, K-1);
			if (cmin == cisimler[i].first) {
				tickets.pb(mp(q+1, i));
			}
			else {
				tickets.pb(mp(q, i));
			}
		}
	}
	int cur = K;
	sort(tickets.begin(), tickets.end());
	for (int i = tickets.size()-1; i >= 0; i--) {
		int x = tickets[i].second;
		while (cur > tickets[i].first) {
			cur--;
			bitinc(queries[cur]);
		}
		int lim = max(cisimler[x].first, cisimler[x].second);
		int a = bitget(524286) - bitget(lim-1);
		kucuk[x] = (a % 2 == 1);
	}
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		if (kucuk[i]) {
			sum += revtbl[ min(cisimler[i].first, cisimler[i].second) ];
		}
		else {
			sum += revtbl[ max(cisimler[i].first, cisimler[i].second) ];
		}
	}
	cout << sum << endl;
 
	return 0;
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	888 KB	Output is correct
2	Correct	5 ms	1052 KB	Output is correct
3	Correct	6 ms	1140 KB	Output is correct
4	Correct	6 ms	1428 KB	Output is correct
5	Correct	7 ms	1464 KB	Output is correct
6	Correct	7 ms	1516 KB	Output is correct
7	Correct	7 ms	1516 KB	Output is correct
8	Correct	7 ms	1548 KB	Output is correct
9	Correct	5 ms	1548 KB	Output is correct
10	Correct	6 ms	1548 KB	Output is correct
11	Correct	7 ms	1548 KB	Output is correct
12	Correct	5 ms	1548 KB	Output is correct
13	Correct	7 ms	1552 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	888 KB	Output is correct
2	Correct	5 ms	1052 KB	Output is correct
3	Correct	6 ms	1140 KB	Output is correct
4	Correct	6 ms	1428 KB	Output is correct
5	Correct	7 ms	1464 KB	Output is correct
6	Correct	7 ms	1516 KB	Output is correct
7	Correct	7 ms	1516 KB	Output is correct
8	Correct	7 ms	1548 KB	Output is correct
9	Correct	5 ms	1548 KB	Output is correct
10	Correct	6 ms	1548 KB	Output is correct
11	Correct	7 ms	1548 KB	Output is correct
12	Correct	5 ms	1548 KB	Output is correct
13	Correct	7 ms	1552 KB	Output is correct
14	Correct	80 ms	6576 KB	Output is correct
15	Correct	140 ms	11792 KB	Output is correct
16	Correct	226 ms	17384 KB	Output is correct
17	Correct	409 ms	22972 KB	Output is correct
18	Correct	328 ms	24128 KB	Output is correct
19	Correct	317 ms	25160 KB	Output is correct
20	Correct	329 ms	26484 KB	Output is correct
21	Correct	340 ms	27564 KB	Output is correct
22	Correct	201 ms	27564 KB	Output is correct
23	Correct	184 ms	27564 KB	Output is correct
24	Correct	134 ms	27564 KB	Output is correct
25	Correct	222 ms	27564 KB	Output is correct
26	Correct	239 ms	27564 KB	Output is correct
27	Correct	222 ms	28748 KB	Output is correct
28	Correct	227 ms	30024 KB	Output is correct
29	Correct	350 ms	33124 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	888 KB	Output is correct
2	Correct	5 ms	1052 KB	Output is correct
3	Correct	6 ms	1140 KB	Output is correct
4	Correct	6 ms	1428 KB	Output is correct
5	Correct	7 ms	1464 KB	Output is correct
6	Correct	7 ms	1516 KB	Output is correct
7	Correct	7 ms	1516 KB	Output is correct
8	Correct	7 ms	1548 KB	Output is correct
9	Correct	5 ms	1548 KB	Output is correct
10	Correct	6 ms	1548 KB	Output is correct
11	Correct	7 ms	1548 KB	Output is correct
12	Correct	5 ms	1548 KB	Output is correct
13	Correct	7 ms	1552 KB	Output is correct
14	Correct	80 ms	6576 KB	Output is correct
15	Correct	140 ms	11792 KB	Output is correct
16	Correct	226 ms	17384 KB	Output is correct
17	Correct	409 ms	22972 KB	Output is correct
18	Correct	328 ms	24128 KB	Output is correct
19	Correct	317 ms	25160 KB	Output is correct
20	Correct	329 ms	26484 KB	Output is correct
21	Correct	340 ms	27564 KB	Output is correct
22	Correct	201 ms	27564 KB	Output is correct
23	Correct	184 ms	27564 KB	Output is correct
24	Correct	134 ms	27564 KB	Output is correct
25	Correct	222 ms	27564 KB	Output is correct
26	Correct	239 ms	27564 KB	Output is correct
27	Correct	222 ms	28748 KB	Output is correct
28	Correct	227 ms	30024 KB	Output is correct
29	Correct	350 ms	33124 KB	Output is correct
30	Runtime error	766 ms	121340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #59225

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