Submission #751489

#	Time	Username	Problem	Language	Result	Execution time	Memory
751489		aebov	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1478 ms	54736 KiB

fortune_telling2

//#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O2")
//#pragma GCC optimize("fast-math")
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
#include<algorithm>
#include<bitset>
#include<map>
#include<iomanip>
#include<set>
#include<string.h>
#include<stack>
#include <list>
#include <numeric>
#include <random>
#include<unordered_map>
#define all(x) x.begin(), x.end()
#define ln (e-s+1)
#define lc (id*2)
#define rc (id*2 + 1)
#define md ((e+s)/2)
#define dm ((e+s)/2+1)
#define pb push_back
#define ll long long 
#define endl '\n'
#define mk make_pair
#define F first
#define pll pair<ll, ll>
#define S second
#define pvv pair<vector<int> , vector<int> > 
#define pii pair<int,int>
#define plll pair<ll, pair<int, int> >
#define ld long double
#define mat vector<vector<ll>>
//#define int long long 
using namespace std;

const int N = (int)2e5 + 5, mod = (int) 1e9 + 7;
int n, k, a[N], b[N], t[N], mn, mx;
vector<int> seg[N << 2];

void build(int id = 1,int s = 1,int e = k){
	if(ln == 1){
		seg[id].pb(t[s]);
		return;
	}build(lc, s, md), build(rc, dm, e);
	for(int x : seg[lc]) seg[id].pb(x);
	for(int x : seg[rc]) seg[id].pb(x);
	sort(seg[id].begin(), seg[id].end());
}
pii get(int l2,int r2,int id = 1,int s = 1,int e = k){
	if(l2 > e || r2 < s) return {mod, 0};
	if( l2 <= s && e <= r2){
		int l = 0, r = seg[id].size() - 1, ans = -1;
		while(l <= r){
			int mid = (l+r) >> 1;
			if(seg[id][mid] >= mn) ans = mid, r = mid - 1;
			else l = mid + 1;
		}
		l = 0, r = seg[id].size() - 1;int ans2 = seg[id].size();
		while(l <= r){
			int mid = (l+r) >> 1;
			if(seg[id][mid] >= mx) ans2 = mid, r = mid - 1;
			else l = mid + 1;
		}
		if(ans == -1) return {mod , 0};
		return {seg[id][ans], seg[id].size() - ans2};
	}
	auto g1 = get(l2, r2, lc, s, md), g2 = get(l2, r2, rc, dm, e);
	return {min(g1.F, g2.F), g1.S + g2.S} ;
}
int 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];
	for(int i = 1; i <= k; i ++) cin >> t[i];
	build();
	ll ret = 0;
	for(int i = 1; i <= n; i ++){
		int l = 1, r = k, ans = k+1;
		mn = min(a[i], b[i]), mx = max(a[i], b[i]);
		while(l <= r){
			int mid = (l+r) >> 1;
			if(get(mid, k).F >= mx) ans = mid, r = mid - 1;
			else l = mid + 1;
		}
	//	cout << "few : " <<  ans << endl;
		if(get(1, ans - 1).F < mx){
			if(get(ans, k).S %2 == 0) ret += mx;
			else ret += mn;
		}
		else{
			if(get(ans , k).S % 2 == 0) ret += a[i];
			else ret += b[i];
		}
	//	cout << ret << endl;
	}cout << ret << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65