제출 #1273243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273243		nthvn	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	147 ms	27028 KiB

fortune_telling2

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
#define mp make_pair
#define cerr if(0)cerr
const int N = 2e5+5;
const int inf = 1e9;
int n,m;
struct Node{
	int a,b,id;
	bool operator <(const Node &o)const{
		return max(a,b) > max(o.a,o.b);
	}
	void print(){
		cerr<<a<<" "<<b<<" "<<"\n";
	}
}s[N];
pii c[N];
struct MinMax{
	pii a[N];
	int tb[N][25];
	void build(){
		for(int i=1;i<=m;i++) a[i]=c[i];
		sort(a+1,a+m+1);
		for(int i=1;i<=m;i++) cerr<<a[i].fi<<" "<<a[i].se<<"\n";
		for(int i=m;i>=1;i--){
			tb[i][0]= a[i].se;
			for(int j=1;i+(1<<j)-1<=m;j++){
				tb[i][j]= max(tb[i][j-1], tb[i+(1<<(j-1))][j-1]);
			}
		}
		cerr<<"\n";
	}
	int get(int l, int r){
		int j= __lg(r-l+1);
		return max(tb[l][j], tb[r-(1<<j)+1][j]);
	}
	int query(int lo, int hi){
		int l = lower_bound(a+1,a+m+1,mp(lo,0))-a;
		int r=  lower_bound(a+1,a+m+1,mp(hi+1,0))-1-a;
		cerr<<l<<" "<<r<<"\n";
		if(l>r) return 0;
		return get(l,r); 
	}
}stnx;

struct BIT{
	int bit[N];
	void update(int i){
		for(;i>0;i-=i&-i) bit[i]+=1;
	}
	int get(int i){
		int ans =0;
		for(;i<=m;i+=i&-i) ans+=bit[i];
		return ans;
	}
}bit;
int ans[N];

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	// if(fopen("TASK.INP", "r")){
		// freopen("TASK.INP", "r", stdin);
		// freopen("TASK.OUT", "w", stdout);
	// }
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int a,b; cin>>a>>b;
		s[i]={a,b,i};
	}
	sort(s+1,s+n+1);
	
	for(int i=1;i<=m;i++) cin>>c[i].fi, c[i].se =i;
	stnx.build();
	sort(c+1,c+m+1,greater<pii>());
	// for(int i=1;i<=n;i++) s[i].print();
	// cerr<<"\n";
	// for(int i=1;i<=m;i++) cerr<<c[i]<<" ";
	
	int pt =1;
	for(int i=1;i<=n;i++){
		int mn = min(s[i].a,s[i].b), mx = max(s[i].a,s[i].b);
		while(pt<=m&&c[pt].fi>=mx) {
			bit.update(c[pt++].se);
		}
		if(s[i].a==s[i].b){
			ans[s[i].id] = s[i].a;
			continue;
		}
		int pos = stnx.query(mn, mx-1);
		cerr<<s[i].a<<" "<<s[i].b<<" "<<pos<<"\n";
		
		int ope = bit.get(pos+1) %2;
		if(pos==0) ans[s[i].id] = ope? s[i].b : s[i].a;
		else ans[s[i].id]= ope? mn: mx;
	}
	ll res=0;
	for(int i=1;i<=n;i++) res+=ans[i];
	cout<<res;
}

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