제출 #1286747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286747		WH8	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	606 ms	97740 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())

struct node {
       int s, e, m, v;
       node *l, *r;
       node (int S, int E){
              s=S, e=E, m=(s+e)/2, v=-1;
              if(s!=e){
                     l=new node(s, m);
                     r=new node(m+1, e);
              }
       }

       int combine(int a, int b){
              return max(a, b);
       }
       void upd(int S, int V){ // range add. 
              if(s==e){
                     v=V;
                     return;
              }
              if (S<=m) l->upd(S,V);
              else if (S>m) r->upd(S,V);
              v=combine(l->v,r->v);
       }
       int qry(int S,int E){
              if((S==s and E==e) or s==e){
                     return v;
              }
              if(E<=m)return l->qry(S,E);
              if(S>m)return r->qry(S,E);
              return combine(l->qry(S,m),r->qry(m+1,E));
       }
} *root;



signed main(){
	int n,k;cin>>n>>k;
	vector<int> disc;
	vector<pair<int,int>> v(n);
	int ans=0;
	for(int i=0;i<n;i++){
		cin>>v[i].f>>v[i].s;
		if(v[i].f==v[i].s)ans+=v[i].f;
		disc.pb(v[i].f);
		disc.pb(v[i].s);
	}
	vector<int> f(k);
	for(int i=0;i<k;i++){
		cin>>f[i];
		disc.pb(f[i]);
	}
	sort(disc.begin(),disc.end());
	disc.erase(unique(disc.begin(),disc.end()),disc.end());
	for(int i=0;i<n;i++) {
		v[i].f=lower_bound(disc.begin(),disc.end(), v[i].f)-disc.begin();
		v[i].s=lower_bound(disc.begin(),disc.end(), v[i].s)-disc.begin();
	}
	root=new node(0,disc.size()-1);
	for(int i=0;i<k;i++){
		f[i]=lower_bound(disc.begin(),disc.end(), f[i])-disc.begin();
		root->upd(f[i], i);
	}
	vector<vector<int>> qry(k);
	vector<int> none;
	for(int i=0;i<n;i++){		
		if(v[i].f==v[i].s)continue;
		int mx=root->qry(min(v[i].f, v[i].s), max(v[i].f,v[i].s)-1);
		if(mx < 0) none.pb(i);
		else qry[mx].pb(i);
	}
	
	vector<int> fw(disc.size(), 0);
	auto update=[&](int x, int v){
		if(x <= 0)return;
		while(x <= (int)disc.size()-1){
			fw[x]+=v;
			x+=(x&(-x));
		}
	};
	auto query=[&](int x)->int{
		int ret=0;
		while(x > 0){
			ret+=fw[x];
			x-=(x&(-x));
		}
		return ret;
	};
	for(int i=k-1;i>=0;i--){
		for(auto qind : qry[i]){
			int flips=query(disc.size()-1)-query(max(v[qind].f,v[qind].s)-1);
			if(flips % 2 == 0) ans += disc[max(v[qind].f,v[qind].s)];
			else ans += disc[min(v[qind].f, v[qind].s)];
		}
		update(f[i], 1);
	}
	for(auto qind : none){
		int flips=query(disc.size()-1)-query(max(v[qind].f,v[qind].s)-1);
		if(flips % 2 == 0) ans += disc[v[qind].f];
		else ans+= disc[v[qind].s];
	}
	cout<<ans;
}

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