제출 #332314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332314		errorgorn	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	1685 ms	159708 KiB

fortune_telling2

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int val=-1;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j){
		val=max(val,j);
		
		if (s==e) return;
		else if (i<=m) l->update(i,j);
		else r->update(i,j);
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,600005);

struct node2{
	int s,e,m;
	int val=0;
	node2 *l,*r;
	
	node2 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	
	void update(int i){
		val++;
		
		if (s==e) return;
		else if (i<=m) l->update(i);
		else r->update(i);
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return l->query(i,m)+r->query(m+1,j);
	}
} *root2=new node2(0,600005);

int n,q;
ii arr[200005];
int brr[200005];

vector<ii> proc;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	rep(x,0,q) cin>>brr[x];
	
	vector<int> uni;
	rep(x,0,n) uni.push_back(arr[x].fi),uni.push_back(arr[x].se);
	rep(x,0,q) uni.push_back(brr[x]);
	
	sort(all(uni));
	uni.erase(unique(all(uni)),uni.end());
	
	map<int,int> id;
	rep(x,0,sz(uni)) id[uni[x]]=x;
	
	rep(x,0,n) arr[x].fi=id[arr[x].fi],arr[x].se=id[arr[x].se];
	rep(x,0,q) brr[x]=id[brr[x]];
	
	rep(x,0,q){
		root->update(brr[x],x);
	}
	
	rep(x,0,n){
		ii temp=arr[x];
		if (temp.fi>temp.se) swap(temp.fi,temp.se);
		
		int val=-1;
		if (temp.fi!=temp.se) val=root->query(temp.fi,temp.se-1);
		
		proc.push_back(ii(val+1,x));
	}
	
	sort(all(proc));
	
	int idx=q;
	ll ans=0;
	while (!proc.empty()){
		while (idx!=proc.back().fi){
			idx--;
			//cout<<"upd: "<<brr[idx]<<endl;
			root2->update(brr[idx]);
		}
		
		int pos=proc.back().se;
		bool orient;
		if (proc.back().fi==0) orient=false;
		else orient=arr[pos].fi<arr[pos].se;
		
		//cout<<idx<<" "<<orient<<endl;
		//cout<<root2->query(max(arr[pos].fi,arr[pos].se),600005)<<endl;
		
		orient^=((root2->query(max(arr[pos].fi,arr[pos].se),600005))%2==1);
		
		//cout<<idx<<" "<<orient<<endl;
		
		if (!orient) ans+=uni[arr[pos].fi];
		else ans+=uni[arr[pos].se];
		
		proc.pop_back();
	}
	
	cout<<ans<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In constructor 'node::node(int, int)':
fortune_telling2.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
fortune_telling2.cpp: In constructor 'node2::node2(int, int)':
fortune_telling2.cpp:64:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

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