Submission #1222450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222450		emad234	Teams (IOI15_teams)	C++20	0 / 100	4098 ms	462416 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mxN = (1 << 22) + 1;
using namespace std;
struct node{
  node *l,*r;
  int val;
	node(node* L,node* R,int V): l(L), r(R), val(V){}
  node(): l(0), r(0), val(0){}
};
int offset;
int query(int l,int r,int s,int e,node* cur){
  if(l > e && r < s) return 0;
  if(l >= s && r <= e) return cur->val;
  int md = (l + r) / 2;
  int op1 = 0,op2 = 0;
  if(cur->l != 0) op1 = query(l,md,s,e,cur->l);
  if(cur->r != 0) op2 = query(md + 1,r,s,e,cur->r);
  return op1 + op2;
}
node* update(int l,int r,int ind,int val,node* cur){
  if(l == r) return new node(0,0, cur->val + val);
  node *L = cur->l, *R = cur->r;
  int md = (l + r) / 2;
  if(md >= ind) L = update(l,md,ind,val,cur->l);
  else R = update(md + 1,r,ind,val,cur->r);
  return new node(L,R,L->val + R->val);
}
node* build(int l = 1,int r = offset){
  if(l == r) return new node();
  int md = (l + r) / 2;
  node *cur = new node();
  cur->l = build(l,md);
  cur->r = build(md + 1,r);
  cur->val = 0;
  return cur;
}
void printseg(node* cur){
	queue<node*>q;
	q.push(cur);
	int ex = 1;
	int i = 0;
	while(q.size()){
		i++;
		auto u = q.front();
		q.pop();
		cout<<u->val<<' ';
		if(ex * 2 - 1 == i){
			cout<<'\n';
			ex *= 2;
		}
		if(u->l != 0) q.push(u->l);
		if(u->r != 0) q.push(u->r);
	}
}
struct student{
	int F,S,id;
	friend bool operator<(student a, student b){
		return tie(a.F,a.S,a.id) < tie(b.F,b.S,b.id);
	}
};
int id[mxN];
vector<student>v;
map<student,int>mp;
vector<node*>root;
int loc[mxN];
node* bg[mxN],* ed[mxN];
void create(){
	sort(v.begin(),v.end());
	int i = 1;
	for(auto &x : v){
		swap(x.F,x.S);
		mp[x] = i++;
	}
	sort(v.begin(),v.end());
	i = 1;
	for(int i = 1;i < offset;i++){
		loc[i] = mp.lower_bound({i,0,0})->S;
		// cout<<loc[i]<<' ';
	}
	// cout<<'\n';
	for(i = 0;i < v.size();i++){
		id[i] = mp[v[i]];
		swap(v[i].F,v[i].S);
	}
	sort(v.begin(),v.end());
	root.push_back(build());
	bg[0] = root[0];
	ed[0] = root[0];
	int j = 0;
	for(i = 0;i < v.size();i++){
		root.push_back(update(1,offset,id[i],1,root.back()));
		while(j < v[i].F){
			bg[j] = root[i];
			ed[j] = root[i];
			j++;
		}
		if(bg[v[i].F] == NULL) bg[v[i].F] = root[i + 1];
		ed[v[i].F] = root[i + 1];
	}
	while(j < offset){
		bg[j] = root.back();
		ed[j] = root.back();
		j++;
	}
	// for(int i = 0;i < offset;i++){
	// 	cout<<ed[i]<<' ';
	// }
	// cout<<'\n';
}
void init(int N, int A[], int B[]) {
	int mx = 0;
	for(int i = 0;i < N;i++){
		mx = max(mx,B[i]);
		v.push_back({A[i],B[i],i});
	}
	offset = exp2(ceil(log2(mx * 2 + 1)));
	create();
}

int can(int M, int K[]) {
	stack<pii>st;
	st.push({1,offset + 1});
	for(int i = 0;i < M;i++){
		int sum = 0;
		int s;
		int e,e1 = loc[K[i]] - 1;
		// if(st.size()){
		// 	cout<<st.top().F<<' '<<st.top().S<<'\n';
		// }
		// cout<<"NOW RUNNING "<<K[i]<<": \n";
		while(st.size() && sum < K[i]){
			s = st.top().F;
			e = e1 + 1;
			e1 = st.top().S;
			int num = query(1,offset,e,e1 - 1,ed[K[i]]) - query(1,offset,e,e1 - 1,ed[s - 1]);
			// cout<<K[i]<<' '<<sum<<' '<<s<<' '<<e<<' '<<e1<<'\n';
			// cout<<ed[K[i]]<<' '<<bg[s - 1]<<' '<<num<<'\n';
			if(sum + num >= K[i]){
				int l = e,r = e1 - 1;
				int md;
				while(l < r){
					int md = (l + r) / 2;
					if(sum + query(1,offset,l,md,ed[K[i]]) - query(1,offset,l,md,ed[s - 1]) >= K[i]) r = md;
					else l = md + 1;
				}
				sum = K[i];
				// cout<<l<<" TEST\n";
				st.push({K[i],l});
				break;
			}
			st.pop();
		}
		if(sum != K[i]) {
			// cout<<0<<'\n';
			return 0;
		}
	}
	// cout<<1<<'\n';
	return 1;
}

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