Submission #300680

#	Time	Username	Problem	Language	Result	Execution time	Memory
300680		errorgorn	Comparing Plants (IOI20_plants)	C++14	44 / 100	1959 ms	56056 KiB

plants

    #include "plants.h"
     
    #include <bits/stdc++.h>
    using namespace std;
     
    #define ll long long
    #define ii pair<ll,ll>
    #define fi first
    #define se second
     
    #define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
    #define all(x) (x).begin(),(x).end()
    #define sz(x) (int) (x).size()
     
    const ll INF=1e18;
     
    struct node{
    	int s,e,m;
    	ii val;
    	ll lazy=0;
    	node *l,*r;
    	
    	node (int _s,int _e){
    		s=_s,e=_e,m=s+e>>1;
    		
    		val=ii(0,s);
    		if (s!=e){
    			l=new node(s,m);
    			r=new node(m+1,e);
    		}
    	}
    	
    	void propo(){
    		if (lazy){
    			val.fi+=lazy;
    			
    			if (s!=e){
    				l->lazy+=lazy;
    				r->lazy+=lazy;
    			}
    			
    			lazy=0;
    		}
    	}
    	
    	void update(int i,int j,ll k){
    		propo();
    		if (s==i && e==j) lazy+=k;
    		else{
    			if (j<=m) l->update(i,j,k);
    			else if (m<i) r->update(i,j,k);
    			else l->update(i,m,k),r->update(m+1,j,k);
    			
    			l->propo(),r->propo();
    			val=min(l->val,r->val);
    		}
    	}
    	
    	int query(int i){
    		propo();
    		
    		if (s==e) return val.fi;
    		else if (i<=m) return l->query(i);
    		else return r->query(i);
    	}
    } *root,*root2;
     
    int n;
    void update(int i,int j,ll k){
    	//cout<<i<<" "<<j<<" "<<k<<endl;
    	if (i<=j) root->update(i,j,k);
    	else root->update(i,n-1,k),root->update(0,j,k);
    }
     
    void update2(int i,int j,ll k){
    	//cout<<i<<" "<<j<<endl;
    	if (i<=j) root2->update(i,j,k);
    	else root2->update(i,n-1,k),root2->update(0,j,k);
    }
     
    vector<int> construct_fast(vector<int> v,int k){
    	n=sz(v);
    	vector<int> ans(n,0);
    	
    	root=new node(0,n-1);
    	root2=new node(0,n-1);
    	
    	rep(x,0,n) root->update(x,x,v[x]),root2->update(x,x,v[x]);
    	
    	while (root2->val.fi==0){
    		int pos=root2->val.se;
    		root2->update(pos,pos,INF);
    		update((pos+1)%n,(pos+(k-1))%n,1);
    	}
    	
    	rep(val,n,0){
    		int idx=root->val.se;
    		//cout<<"curr: "<<idx<<" "<<root->val.fi<<endl;
    		
    		ans[idx]=val;
    		
    		update((idx+1)%n,(idx+(k-1))%n,-1);
    		
    		update((idx-(k-1)+n)%n,(idx-1+n)%n,-1);
    		update2((idx-(k-1)+n)%n,(idx-1+n)%n,-1);
    		
    		//rep(x,0,n) cout<<root2->query(x)<<" "; cout<<endl;
    		
    		while (root2->val.fi==0){
    			int pos=root2->val.se;
    			root2->update(pos,pos,INF);
    			update((pos+1)%n,(pos+(k-1))%n,1);
    		}
    		
    		root->update(idx,idx,INF);
    	}
    	
    	return ans;
    }
     
    vector<int> arr;
     
    void init(int k, std::vector<int> r) {
    	arr=construct_fast(r,k);
    	
    	//for (auto &it:arr) cout<<it<<" "; cout<<endl;
    }
     
    int compare_plants(int x, int y) {
    	if (arr[x]<arr[y]) return -1;
    	else return 1;
    }

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25