Submission #669231

#	Time	Username	Problem	Language	Result	Execution time	Memory
669231		penguin133	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	288 ms	39124 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m,q;
int ft[200005];
void upd(int p, int v){
	for(;p<=m;p+=(p & -p))ft[p] += v;
}

int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}

pi A[200005];
bool cmp(pi a, pi b){
	return max(a.fi, a.se) < max(b.fi, b.se);
}

pi Q[200005];
struct node{
	int s,e,m,val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		if(s != e)l = new node(s, m), r = new node(m+1, e), val = max(l->val, r->val);
		else val = Q[s].se;
	}
	int query(int a, int b){
		if(a == s && b == e)return val;
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return max(l->query(a, m), r->query(m+1, b));
	}
}*root;
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se;
	sort(A+1, A+n+1, cmp);
	for(int i=1;i<=m;i++)cin >> Q[i].fi, Q[i].se = i, upd(i, 1);
	sort(Q+1, Q+m+1);
	root = new node(1, m);
	int in = 1, cur = 0;
	Q[0].fi = -1e9;
	int ans = 0;
	for(int i=1;i<=n;i++){
		while(in <= m && Q[in].fi < max(A[i].fi, A[i].se))cur = max(cur, Q[in].se), upd(Q[in].se, -1), in++;
		int tmp;
		if(Q[in-1].fi < min(A[i].fi, A[i].se)){
			tmp = m - in + 1;
			ans += (tmp%2 ? A[i].se : A[i].fi);
		}
		else {
			int lo = 1, hi = in, ans2 = in + 1;
			while(lo <= hi){
				int mid = (lo + hi)>>1;
				if(Q[mid].fi >= min(A[i].fi, A[i].se))ans2 = mid, hi = mid - 1;
				else lo = mid + 1;
			}
			tmp = root->query(ans2, in - 1);
			tmp = query(m) - query(tmp);
			//cout << tmp << '\n';
			ans += (tmp%2 ? min(A[i].fi, A[i].se) : max(A[i].fi, A[i].se));
		}
		//cout << ans << ' ' << A[i].fi << ' ' << A[i].se << '\n';
	}
	cout << ans;
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

fortune_telling2.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~

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