Submission #1243136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243136		settop	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	149 ms	25768 KiB

fortune_telling2

#include<bits/stdc++.h>
 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define int long long
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define eb emplace_back
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
#define sz(x) (int)x.size()
const int MAXN=6e5+10;
const int MAXL=1e2+10;
const long long inf=1e17;
const int MOD=1e9+7;
 
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
typedef tuple<int,int,int,int> squad;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int mn,sum;
};

map<int,int> mp,rev;
int n,k;
vector<pii> v;
vector<trio>line;
vector<int> q,ord;
node seg[4*MAXN];

node merge(node a,node b){
	node c;
	c.sum=a.sum+b.sum;
	c.mn=min(a.mn,b.mn);
	return c;
}

void build(int ind,int l,int r){
	if(l==r){
		seg[ind].mn=q[l];
		seg[ind].sum=1;
		return;
	}
	int m=(l+r)/2;
	build(2*ind,l,m); build(2*ind+1,m+1,r);
	seg[ind]=merge(seg[2*ind],seg[2*ind+1]);
}

int query(int ind,int l,int r,int val){
	if(seg[ind].mn>=val) return -1;
	if(l==r) return l;
	if(seg[2*ind+1].mn<val) return query(2*ind+1,(l+r)/2+1,r,val);
	return query(2*ind,l,(l+r)/2,val);
}

int query2(int ind,int l,int r,int a,int b){
	if(a>r || l>b) return 0;
	if(a<=l && b>=r) return seg[ind].sum;
	int m=(l+r)/2;
	return query2(2*ind,l,m,a,b)+query2(2*ind+1,m+1,r,a,b);
}

void updt(int ind,int l,int r,int a){
	if(a<l || a>r) return;
	if(l==r){
		seg[ind].sum=0;
		seg[ind].mn=inf;
		return;
	}
	int m=(l+r)/2; updt(2*ind,l,m,a); updt(2*ind+1,m+1,r,a);
	seg[ind]=merge(seg[2*ind],seg[2*ind+1]);
}

int32_t main(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("threesum.in","r",stdin);
	//freopen("threesum.out","w",stdout);
	
	cin>>n>>k;
	v.resize(n),q.resize(k);

	for(auto &u:v) cin>>u.F>>u.S;

	for(auto &u:q) cin>>u;

	build(1,0,k-1);

	fall(i,0,n-1) line.pb({min(v[i].F,v[i].S),0,i});
	fall(i,0,k-1) line.pb({q[i],1,i});


	sort(all(line));
	int ans=0;
	for(auto [a,b,c]:line){
		if(!b){
			auto [u,j]=v[c];
			int x=query(1,0,k-1,max(u,j));
			int quan=query2(1,0,k-1,x+1,k-1);
			quan%=2;
			if(x!=-1 && u<j) swap(u,j);
			if(quan) ans+=j;
			else ans+=u; 
		}
		else updt(1,0,k-1,c);
		
	}
	cout<<ans<<"\n";
}

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