Submission #235378

#	Time	Username	Problem	Language	Result	Execution time	Memory
235378		Atalasion	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	839 ms	82272 KiB

fortune_telling2

//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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65