Submission #1222354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222354		jklepec	Teams (IOI15_teams)	C++17	0 / 100	1889 ms	452448 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second.first
#define remain second.second
using namespace std;
const int N=5e5+2,mod=1e9+7;
struct nd{
	nd *l,*r;
	int val;
	nd(int value = 0,nd *le = NULL, nd *ri = NULL){
		l = le,r = ri,val = value;
	}
	nd(nd *node){
		l = node -> l,r = node -> r,val = node -> val;
	}
};

int n;
pair<int,int> rng[N];
int lef[N];
vector<nd*>v(N+1);

void update(int idx,nd *node,int l = 1,int r = n){
	if(l == r){
		node -> val ++;
		return;
	}
	int mid = (l + r)/2;


	if(idx <= mid){
  		if(node -> l)
			node -> l = new nd(node -> l);
  		else
  			node -> l = new nd();
		update(idx,node -> l,l,mid);
	}
	else{
    	if(node -> r)
			node -> r = new nd(node -> r);
      	else
      		node -> r = new nd();
		update(idx,node -> r,mid+1,r);
	}
	node -> val = (node -> l ? node -> l -> val : 0) + (node -> r ? node -> r -> val : 0);
}
int get(int ql, int qr,nd *node,nd *minus = NULL,int l = 1,int r = n){
	if(r < ql || qr < l) return 0;
	if(ql <= l && r <= qr) return (node -> val) - (minus ? minus -> val : 0);
	if(minus == NULL){
		minus = new nd();
		minus -> l = minus, minus -> r = minus;
	}
	
	int mid = (l + r)/2;
	return (node->l ? get(ql,qr,node -> l,minus -> l,l,mid) : 0) + (node-> r ? get(ql,qr,node -> r,minus -> r,mid + 1,r) : 0);
}
void init(int en, int A[], int B[]) {
	n=en;
	for(int i = 1;i <= n;i++){
    	rng[i].F = A[i-1],rng[i].second = B[i-1];
    }
    sort(rng+1,rng+n+1);
    v[0] = new nd();
    for(int i = 1;i <= n;i++){
    	lef[i] = rng[i].F;
    	v[i] = new nd(v[i-1]);
    	update(rng[i].second,v[i]);
    }
}

int can(int m, int K[]) {
	int x[m+1];
	x[0]=0;
	for(int i = 1;i <= m;i++)
		x[i] = K[i-1];
	sort(x+1,x + m + 1);
	bool ok = 1;
	vector<pair<nd*,pair<int,int>>>st;
	st.push_back({new nd(),{n,0}});
	for(int i = 1;i <= m;i++){
		int u = upper_bound(lef+1,lef+n+1,x[i])-lef-1;
		//cout<<"u "<<u<<endl;
		nd *root = v[u];
		int ans = x[i];
        while (i < m && x[i] == x[i+1])
            i++, ans += x[i];
		int b = x[i],e = -1;
        while(b > st.back().S){
            st.pop_back();
            //cout<<b<<" "<<st.back().S;
        }
		while(st.size()){
			//cout<<b<<" "<<st.back().S;
			//cout<<"get+remain: "<<gr<<endl;
			
			int gr = get(b,st.back().S,root,st.back().F) + st.back().remain;
			if(ans <= gr)
				break;
			ans -= gr;
			b = st.back().S+1;
			st.pop_back();
		}

		if(st.size())
			e = st.back().S;
		else
			return 0;
		
		nd *minus = st.back().F;
		int last = e,remaining=0;
        assert(ans <= get(b,e,root,minus) + st.back().remain);
		while(b <= e){
			int mid = (b + e)/2;
			ll cur = get(b,mid,root,minus);
			if(mid == st.back().S)
				cur+=st.back().remain;
			if(cur >= ans){
				last = mid,e = mid - 1;
				remaining = cur - ans;
			}
			else
				b=mid+1;
		}
		//cout<<"last: "<<last<<" remaining: "<<remaining<<"\n";
        assert(!st.size() || st.back().S >= last);
		if (st.size() && st.back().S == last)
			st.pop_back();
		st.push_back({root,{last,remaining}});
	}
	return 1;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23