oj.uz

Submission #235378

# Submission time Handle Problem Language Result Execution time Memory
235378 2020-05-28T07:30:22 Z Atalasion Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 839 ms 82272 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

vector<int> seg[N << 2], T;
vector<pii> t;
int n, a[N], b[N], k, A[N], ans, aa[N], bb[N];

void build(int id, int l, int r){
	if (r - l == 1){
		seg[id].pb(A[l]);
		return;
	}
	int md = (l + r) >> 1;
	build(id << 1, l, md);
	build(id << 1 | 1, md, r);
	for (auto u:seg[id << 1]) seg[id].pb(u);
	for (auto u:seg[id << 1 | 1]) seg[id].pb(u);
	sort(all(seg[id]));
}

int get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq) return 0;
	if (lq <= l && r <= rq){
		return seg[id].back();
	}
	int md = (l + r) >> 1;
	return max(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}

int Get(int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq) return 0;
	if (lq <= l && r <= rq){
		int tt = lower_bound(all(seg[id]), x) - seg[id].begin();
		return seg[id].size() - tt;
	}
	int md = (l + r) >> 1;
	return (Get(id << 1, lq, rq, x, l, md) + Get(id << 1 | 1, lq, rq, x, md, r));
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i]; aa[i] = a[i]; bb[i] = b[i];}
	for (int i = 1; i <= k; i++){
		int x;
		cin >> x;
		t.pb({x, i});
		T.pb(x);
	}
	sort(all(t));
	sort(all(T));
	for (int i = 1; i <= n; i++){
		int x = lower_bound(all(T), a[i]) - T.begin() + 1;
		a[i] = x;
		x = lower_bound(all(T), b[i]) - T.begin() + 1;
		b[i] = x;
	}
	//cout << '\n';
	for (int i = 1; i <= k; i++) A[i] = t[i - 1].S;
	build(1, 1, N + 1);
	for (int i = 1; i <= n; i++){
		//cout << a[i] << ' ' << b[i] << '\n';
		int x = get(1, min(a[i], b[i]), max(a[i], b[i]), 1, N + 1);
		if (a[i] - b[i] == 0) x = 0;
		int tt = Get(1, max(a[i], b[i]), k + 1, x, 1, N + 1);
		//cout << x << '\n';
		//cout << tt << '\n';
		if (x == 0){
			if (tt % 2 == 1) ans += bb[i];
			else ans += aa[i];
			continue;
		}
		if (tt % 2 == 1) ans += min(aa[i], bb[i]);
		else ans += max(aa[i], bb[i]);
	}
	cout << ans;


	return 0;
}
/*
1 6
2 5
1 2 6 4 5 1
*/

Compilation message

fortune_telling2.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
fortune_telling2.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 63344 KB Output is correct
2 Correct 158 ms 63340 KB Output is correct
3 Correct 155 ms 63340 KB Output is correct
4 Correct 154 ms 63340 KB Output is correct
5 Correct 155 ms 63340 KB Output is correct
6 Correct 154 ms 63340 KB Output is correct
7 Correct 153 ms 63340 KB Output is correct
8 Correct 163 ms 63284 KB Output is correct
9 Correct 156 ms 63340 KB Output is correct
10 Correct 151 ms 63340 KB Output is correct
11 Correct 162 ms 63340 KB Output is correct
12 Correct 164 ms 63596 KB Output is correct
13 Correct 158 ms 63340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 63344 KB Output is correct
2 Correct 158 ms 63340 KB Output is correct
3 Correct 155 ms 63340 KB Output is correct
4 Correct 154 ms 63340 KB Output is correct
5 Correct 155 ms 63340 KB Output is correct
6 Correct 154 ms 63340 KB Output is correct
7 Correct 153 ms 63340 KB Output is correct
8 Correct 163 ms 63284 KB Output is correct
9 Correct 156 ms 63340 KB Output is correct
10 Correct 151 ms 63340 KB Output is correct
11 Correct 162 ms 63340 KB Output is correct
12 Correct 164 ms 63596 KB Output is correct
13 Correct 158 ms 63340 KB Output is correct
14 Correct 171 ms 64236 KB Output is correct
15 Correct 188 ms 65132 KB Output is correct
16 Correct 223 ms 66036 KB Output is correct
17 Correct 244 ms 66928 KB Output is correct
18 Correct 258 ms 66980 KB Output is correct
19 Correct 253 ms 66924 KB Output is correct
20 Correct 246 ms 66924 KB Output is correct
21 Correct 232 ms 66800 KB Output is correct
22 Correct 211 ms 66412 KB Output is correct
23 Correct 218 ms 66416 KB Output is correct
24 Correct 216 ms 66544 KB Output is correct
25 Correct 217 ms 66416 KB Output is correct
26 Correct 226 ms 66728 KB Output is correct
27 Correct 261 ms 66924 KB Output is correct
28 Correct 232 ms 66928 KB Output is correct
29 Correct 239 ms 66932 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 63344 KB Output is correct
2 Correct 158 ms 63340 KB Output is correct
3 Correct 155 ms 63340 KB Output is correct
4 Correct 154 ms 63340 KB Output is correct
5 Correct 155 ms 63340 KB Output is correct
6 Correct 154 ms 63340 KB Output is correct
7 Correct 153 ms 63340 KB Output is correct
8 Correct 163 ms 63284 KB Output is correct
9 Correct 156 ms 63340 KB Output is correct
10 Correct 151 ms 63340 KB Output is correct
11 Correct 162 ms 63340 KB Output is correct
12 Correct 164 ms 63596 KB Output is correct
13 Correct 158 ms 63340 KB Output is correct
14 Correct 171 ms 64236 KB Output is correct
15 Correct 188 ms 65132 KB Output is correct
16 Correct 223 ms 66036 KB Output is correct
17 Correct 244 ms 66928 KB Output is correct
18 Correct 258 ms 66980 KB Output is correct
19 Correct 253 ms 66924 KB Output is correct
20 Correct 246 ms 66924 KB Output is correct
21 Correct 232 ms 66800 KB Output is correct
22 Correct 211 ms 66412 KB Output is correct
23 Correct 218 ms 66416 KB Output is correct
24 Correct 216 ms 66544 KB Output is correct
25 Correct 217 ms 66416 KB Output is correct
26 Correct 226 ms 66728 KB Output is correct
27 Correct 261 ms 66924 KB Output is correct
28 Correct 232 ms 66928 KB Output is correct
29 Correct 239 ms 66932 KB Output is correct
30 Correct 355 ms 72544 KB Output is correct
31 Correct 452 ms 74508 KB Output is correct
32 Correct 583 ms 77000 KB Output is correct
33 Correct 827 ms 82016 KB Output is correct
34 Correct 339 ms 72036 KB Output is correct
35 Correct 839 ms 82020 KB Output is correct
36 Correct 805 ms 82152 KB Output is correct
37 Correct 832 ms 82144 KB Output is correct
38 Correct 804 ms 82180 KB Output is correct
39 Correct 813 ms 82144 KB Output is correct
40 Correct 616 ms 81968 KB Output is correct
41 Correct 806 ms 82144 KB Output is correct
42 Correct 827 ms 82144 KB Output is correct
43 Correct 451 ms 81376 KB Output is correct
44 Correct 463 ms 81392 KB Output is correct
45 Correct 458 ms 81372 KB Output is correct
46 Correct 556 ms 80224 KB Output is correct
47 Correct 562 ms 80084 KB Output is correct
48 Correct 681 ms 82272 KB Output is correct
49 Correct 641 ms 82124 KB Output is correct