oj.uz

Submission #59225

# Submission time Handle Problem Language Result Execution time Memory
59225 2018-07-21T09:10:04 Z gusfring Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 766 ms 121340 KB 
#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

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

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

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