Submission #671047

#	Time	Username	Problem	Language	Result	Execution time	Memory
671047		alvingogo	Teams (IOI15_teams)	C++14	100 / 100	1182 ms	232824 KiB

teams

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
	struct no{
		int lch=-1,rch=-1,val=0;
	};
	vector<no> st;
	int newe(no x){
		st.push_back(x);
		return st.size()-1;
	}
	void pull(int x){
		st[x].val=st[st[x].lch].val+st[st[x].rch].val;
	}
	int build(int L,int R){
		if(L==R){
			int x=newe({-1,-1,0});
			return x;
		}
		int m=(L+R)/2;
		int a=build(L,m);
		int b=build(m+1,R);
		int x=newe({a,b,0});
		return x;
	}
	int update(int v,int L,int R,int p){
		if(L==R){
			int x=newe(st[v]);
			st[x].val++;
			return x;
		}
		int m=(L+R)/2;
		if(p<=m){
			int a=update(st[v].lch,L,m,p);
			int x=newe(st[v]);
			st[x].lch=a;
			pull(x);
			return x;
		}
		else{
			int b=update(st[v].rch,m+1,R,p);
			int x=newe(st[v]);
			st[x].rch=b;
			pull(x);
			return x;
		}
	}
	int query(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].val;
		}
		int m=(L+R)/2;
		if(r<=m){
			return query(st[v].lch,L,m,l,r);
		}
		else if(l>m){
			return query(st[v].rch,m+1,R,l,r);
		}
		else{
			return query(st[v].lch,L,m,l,m)+query(st[v].rch,m+1,R,m+1,r);
		}
	}
	int bs(int v1,int v2,int L,int R,int k){
		if(L==R){
			return L;
		}
		int s=st[st[v2].lch].val-st[st[v1].lch].val;
		int m=(L+R)/2;
		if(s>=k){
			return bs(st[v1].lch,st[v2].lch,L,m,k);
		}
		else{
			return bs(st[v1].rch,st[v2].rch,m+1,R,k-s);
		}
	}
}st;

int n;
vector<int> rt;
int get(int l,int r,int u,int d){
	if(l>r || u>d){
		return 0;
	}
	return st.query(rt[r],0,n,u,d)-(l==0?0:st.query(rt[l-1],0,n,u,d));
}

vector<int> lis;
void init(int N,int a[],int b[]){
	n=N;
	lis.clear();
	vector<pair<int,int> > c;
	for(int i=0;i<n;i++){
		c.push_back({b[i],a[i]});
	}
	sort(c.begin(),c.end());
	for(int i=0;i<n;i++){
		lis.push_back(c[i].fs);
		c[i].fs=i;
	}
	vector<vector<int> > d(n+1);
	for(int i=0;i<n;i++){
		d[c[i].sc].push_back(c[i].fs);
	}
	rt.resize(n+1);
	rt[0]=st.build(0,n);
	for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(auto h:d[i]){
			rt[i]=st.update(rt[i],0,n,h);
		}
	}
}
struct DQ{
	int id,mx,sum;
};
int can(int m,int k[]){
	sort(k,k+m);
	vector<DQ> v;
	v.push_back({0,n,0});
	int uu=0;
	for(int i=0;i<m;i++){
		if(i<m-1 && k[i]==k[i+1]){
			uu+=k[i];
			continue;
		}
		int a=k[i];
		k[i]+=uu;
		uu=0;
		int nxt=0;
		int lt=lower_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
		while(v.size()){
			auto h=v.back();
			if(h.mx<lt){
				v.pop_back();
				continue;
			}
			h.sum=max(h.sum,get(h.id+1,a,0,lt));
			int zz=get(h.id+1,a,0,h.mx)-h.sum;
			if(zz<k[i]){
				k[i]-=zz;
				v.pop_back();
				if(v.size()){
					v.back().sum+=h.sum+zz;
				}
			}
			else{
				h.sum+=k[i];
				nxt=st.bs(rt[h.id],rt[a],0,n,h.sum);
				k[i]=0;
				v.back()=h;
				break;
			}
		}
		if(k[i]){
			return 0;
		}
		v.push_back({a,nxt,0});
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int ST::newe(ST::no)':
teams.cpp:16:19: warning: conversion from 'std::vector<ST::no>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |   return st.size()-1;
      |          ~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:136:58: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  136 |   int lt=lower_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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