oj.uz

Submission #975543

# Submission time Handle Problem Language Result Execution time Memory
975543 2024-05-05T12:55:54 Z falaz Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 301 ms 113852 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
//#define endl '\n'

#define F first
#define S second

#define SZ(a) int32_t(a.size())

namespace RMQ {
	const int N = 6e5 + 7, LG = 20;
	int rmq[LG][N];
	void add(int i, int k) {
		rmq[0][i] = k;
		return;
	}
	void pre(int n) {
		for (int i = 0; i < LG - 1; ++i)
			for (int j = 0; j + (2 << i) <= n; ++j)
				rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
		return;
	}
	int get(int l, int r) {
		int L = __lg(r - l);	
		return max(rmq[L][l], rmq[L][r - (1 << L)]);
	}
}

namespace FEN {
	const int N = 6e5 + 7;
	bitset<N> fen;
	bool f;
	void add(int i) {
		f = !f;
		i++;
		for (; i < N; i += (i & -i))
			fen[i] = !fen[i];
		return;
	}
	bool get(int i) {
		i++;
		bool ret = 0;
		for (; i; i -= (i & -i)) {
			ret ^= fen[i];
		}
		return ret;
	}
	bool gets(int i) {
		return f ^ get(i - 1);
	}

}

const int N = 6e5 + 7;

struct rmp {
	int mn, mx;
}mp[N];

int n, q, a[N], b[N], t[N], ans;
pair<int, int> f[N];
vector<int> com, sv1[N];
vector<pair<int, int>> sv2;

void ip() {
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		mp[i].mn = min(a[i], b[i]);
		mp[i].mx = max(a[i], b[i]);
		com.push_back(a[i]);
		com.push_back(b[i]);
	}
	for (int i = 0; i < q; ++i) {
		cin >> t[i];
		com.push_back(t[i]);
	}
	return;
}

void compres() {
	sort(com.begin(), com.end());
	com.resize(unique(com.begin(), com.end()) - com.begin());

	for (int i = 0; i < n; i++)
		a[i] = lower_bound(com.begin(), com.end(), a[i]) - com.begin(),
		b[i] = lower_bound(com.begin(), com.end(), b[i]) - com.begin();
	for (int i = 0; i < q; i++)
		t[i] = lower_bound(com.begin(), com.end(), t[i]) - com.begin();
	return;
}

void pre() {
	for (int i = 0; i < q; ++i)
		f[i] = {t[i], i};
	sort(f, f + q);
	for (int i = 0; i < q; ++i)
		RMQ::add(i, f[i].S);
	RMQ::pre(q);
	return;
}

void solve() {
	for (int i = 0; i < n; ++i) {
		int mn = min(a[i], b[i]), mx = max(a[i], b[i]), l;
		pair<int, int> a1 = {mn, -1}, b1 = {mx, -1};
		int bsn = lower_bound(f, f + q, a1) - f;
		int bsx = upper_bound(f, f + q, b1) - f;
		(bsn >= bsx) ? l = - 1 : l = RMQ::get(bsn, bsx);
	//	cout << mn << " " << mx << " " << bsn << " " << bsx << " " << l << endl;
		bool pb = (a[i] <= b[i]);
		(l == -1) ? sv2.push_back({pb , i}) : sv1[l].push_back(i);
	}
	for (int i = q - 1;  ~i; --i) {
	//	cout << "gg" << i << " " << sv1[i].size() << endl;
		for (auto j : sv1[i]) {
			int l = 0;
			int mx = max(a[j], b[j]);
			l ^= FEN::gets(mx);
			ans += (l ? mp[j].mn : mp[j].mx);
		}
		FEN::add(t[i]);
	}

	for (auto i: sv2) {
		int l = i.F;
		int mx = max(a[i.S], b[i.S]);
		l ^= FEN::gets(mx);
		ans += (l ? mp[i.S].mn : mp[i.S].mx);
	}
	return;
}

void op() {
	cout << ans;
	return;
}

void run() {
	ip();
	compres();
	pre();
	solve();
	op();
	return;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	run();

	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43600 KB Output is correct
2 Correct 9 ms 43624 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 8 ms 43624 KB Output is correct
5 Correct 8 ms 43684 KB Output is correct
6 Correct 8 ms 43804 KB Output is correct
7 Correct 9 ms 43816 KB Output is correct
8 Correct 8 ms 43612 KB Output is correct
9 Correct 9 ms 43688 KB Output is correct
10 Correct 8 ms 43800 KB Output is correct
11 Correct 8 ms 43612 KB Output is correct
12 Correct 8 ms 43612 KB Output is correct
13 Correct 9 ms 43612 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43600 KB Output is correct
2 Correct 9 ms 43624 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 8 ms 43624 KB Output is correct
5 Correct 8 ms 43684 KB Output is correct
6 Correct 8 ms 43804 KB Output is correct
7 Correct 9 ms 43816 KB Output is correct
8 Correct 8 ms 43612 KB Output is correct
9 Correct 9 ms 43688 KB Output is correct
10 Correct 8 ms 43800 KB Output is correct
11 Correct 8 ms 43612 KB Output is correct
12 Correct 8 ms 43612 KB Output is correct
13 Correct 9 ms 43612 KB Output is correct
14 Correct 21 ms 54628 KB Output is correct
15 Correct 34 ms 59344 KB Output is correct
16 Correct 44 ms 61896 KB Output is correct
17 Correct 61 ms 66764 KB Output is correct
18 Correct 55 ms 66768 KB Output is correct
19 Correct 53 ms 66764 KB Output is correct
20 Correct 55 ms 66728 KB Output is correct
21 Correct 51 ms 66884 KB Output is correct
22 Correct 39 ms 66256 KB Output is correct
23 Correct 39 ms 66256 KB Output is correct
24 Correct 40 ms 66256 KB Output is correct
25 Correct 39 ms 66508 KB Output is correct
26 Correct 48 ms 66256 KB Output is correct
27 Correct 56 ms 66764 KB Output is correct
28 Correct 46 ms 66772 KB Output is correct
29 Correct 55 ms 67280 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 43600 KB Output is correct
2 Correct 9 ms 43624 KB Output is correct
3 Correct 10 ms 43612 KB Output is correct
4 Correct 8 ms 43624 KB Output is correct
5 Correct 8 ms 43684 KB Output is correct
6 Correct 8 ms 43804 KB Output is correct
7 Correct 9 ms 43816 KB Output is correct
8 Correct 8 ms 43612 KB Output is correct
9 Correct 9 ms 43688 KB Output is correct
10 Correct 8 ms 43800 KB Output is correct
11 Correct 8 ms 43612 KB Output is correct
12 Correct 8 ms 43612 KB Output is correct
13 Correct 9 ms 43612 KB Output is correct
14 Correct 21 ms 54628 KB Output is correct
15 Correct 34 ms 59344 KB Output is correct
16 Correct 44 ms 61896 KB Output is correct
17 Correct 61 ms 66764 KB Output is correct
18 Correct 55 ms 66768 KB Output is correct
19 Correct 53 ms 66764 KB Output is correct
20 Correct 55 ms 66728 KB Output is correct
21 Correct 51 ms 66884 KB Output is correct
22 Correct 39 ms 66256 KB Output is correct
23 Correct 39 ms 66256 KB Output is correct
24 Correct 40 ms 66256 KB Output is correct
25 Correct 39 ms 66508 KB Output is correct
26 Correct 48 ms 66256 KB Output is correct
27 Correct 56 ms 66764 KB Output is correct
28 Correct 46 ms 66772 KB Output is correct
29 Correct 55 ms 67280 KB Output is correct
30 Correct 112 ms 96828 KB Output is correct
31 Correct 143 ms 101640 KB Output is correct
32 Correct 200 ms 106176 KB Output is correct
33 Correct 301 ms 113092 KB Output is correct
34 Correct 88 ms 96484 KB Output is correct
35 Correct 281 ms 113580 KB Output is correct
36 Correct 289 ms 113068 KB Output is correct
37 Correct 283 ms 112628 KB Output is correct
38 Correct 294 ms 112944 KB Output is correct
39 Correct 297 ms 112488 KB Output is correct
40 Correct 260 ms 113360 KB Output is correct
41 Correct 275 ms 112220 KB Output is correct
42 Correct 279 ms 113332 KB Output is correct
43 Correct 187 ms 113396 KB Output is correct
44 Correct 166 ms 113332 KB Output is correct
45 Correct 168 ms 113852 KB Output is correct
46 Correct 193 ms 110728 KB Output is correct
47 Correct 180 ms 110224 KB Output is correct
48 Correct 228 ms 112680 KB Output is correct
49 Correct 209 ms 113248 KB Output is correct