Submission #421278

#	Time	Username	Problem	Language	Result	Execution time	Memory
421278		errorgorn	Wiring (IOI17_wiring)	C++17	100 / 100	766 ms	33128 KiB

wiring

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

#include "wiring.h"

#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 debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#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());

const ll INF=1e15; //???

vector<ii> v;

struct node{
	int s,e,m;
	ll val=0,lazy=0;
	bool lazyset=false;
	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 propo(){
		if (lazyset){
			val=0;
			
			if (s!=e){
				l->lazy=0;
				l->lazyset=true;
				
				r->lazy=0;
				r->lazyset=true;
			}
			
			lazyset=false;
		}
		
		if (lazy){
			val+=(e-s+1)*lazy;
			
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update_add(int i,int j,ll k){
		propo();
		
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update_add(i,j,k);
			else if (m<i) r->update_add(i,j,k);
			else l->update_add(i,m,k),r->update_add(m+1,j,k);
			
			l->propo(),r->propo();
			val=l->val+r->val;
		}
	}
	
	void update_set(int i,int j){
		propo();
		
		if (s==i && e==j){
			lazy=0;
			lazyset=true;
		}
		else{
			if (j<=m) l->update_set(i,j);
			else if (m<i) r->update_set(i,j);
			else l->update_set(i,m),r->update_set(m+1,j);
			
			l->propo(),r->propo();
			val=l->val+r->val;
		}
	}
	
	ll query(int i,int j){
		propo();
		
		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);
	}
} *root=new node(0,200010);

long long min_total_length(std::vector<int> R, std::vector<int> B) {
	for (auto &it:R) v.pub(ii(it,1));
	for (auto &it:B) v.pub(ii(it,-1));
	
	sort(all(v));
	
	int curr=100005;
	root->update_add(0,curr,-INF);
	root->update_add(curr+1,200010,INF);
	
	int p=0;
	ll ans=0;
	for (auto &it:v){
		root->update_add(0,curr,-(it.fi-p));
		root->update_add(curr+1,200010,it.fi-p);
		p=it.fi;
		
		if (it.se==-1){
			//set all negatives to 0
			//curr++
			
			ans+=root->query(curr+1,curr+1);
			
			int lo=0,hi=200010,mi;
			while (hi-lo>1){
				mi=hi+lo>>1;
				
				if (root->query(mi,mi)<0) lo=mi;
				else hi=mi;
			}
			
			if (curr+1<lo) ans+=root->query(curr+2,lo);
			root->update_set(0,lo);
			
			curr++;
		}
		else{
			//set all positives to 0
			//curr--
			
			ans-=root->query(curr,curr);
			
			int lo=0,hi=200010,mi;
			while (hi-lo>1){
				mi=hi+lo>>1;
				
				if (root->query(mi,mi)>0) hi=mi;
				else lo=mi;
			}
			
			if (hi<curr) ans-=root->query(hi,curr-1);
			root->update_set(hi,200010);
			
			curr--;
		}
		
		//cout<<ans<<" "<<curr<<endl;
		//rep(x,curr-2,curr+4) cout<<root->query(x,x)<<" "; cout<<endl;
	}
	
	return ans;
}

Compilation message (stderr)

wiring.cpp: In constructor 'node::node(int, int)':
wiring.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:147:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |     mi=hi+lo>>1;
      |        ~~^~~
wiring.cpp:166:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |     mi=hi+lo>>1;
      |        ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45