Submission #590019

#	Time	Username	Problem	Language	Result	Execution time	Memory
590019		FatihSolak	Teams (IOI15_teams)	C++17	21 / 100	4086 ms	303684 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define N 500005
#define K 50
using namespace std;
struct node{
	int l = 0,r = 0;
	int val = 0;
}nodes[N * K];
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
	int nwnode = ++cnt;
	nodes[nwnode] = nodes[v];
	if(tl == tr){
		nodes[nwnode].val += val;
		return nwnode;
	}
	int tm = (tl + tr)/2;
	if(pos <= tm){
		if(nodes[v].l == 0){
			nodes[v].l = ++cnt;
		}
		nodes[nwnode].l = upd(nodes[v].l,tl,tm,pos,val);
	}
	else{
		if(nodes[v].r == 0){
			nodes[v].r = ++cnt;
		}
		nodes[nwnode].r = upd(nodes[v].r,tm+1,tr,pos,val);
	}
	nodes[nwnode].val = nodes[nodes[nwnode].l].val + nodes[nodes[nwnode].r].val;
	//cout << nwnode << " " << tl << " " << tr << " " << pos << " " << val << " " << nodes[nwnode].val << " " << nodes[nwnode].l << " " << nodes[nwnode].r << endl;
	return nwnode;
}
int get(int v,int tl,int tr,int l,int r){
	if(v == 0 || tr < l || r < tl)
		return 0;
	if(l <= tl && tr <= r){
		return nodes[v].val;
	}
	int tm = (tl + tr)/2;
	return get(nodes[v].l,tl,tm,l,r) + get(nodes[v].r,tm+1,tr,l,r);
}
int root[N];
int n;
multiset<int> s[N];
vector<int> tmp[N];
void init(int n_, int a[], int b[]) {
	n = n_;
	for(int i = 0;i<n;i++){
		tmp[a[i]].push_back(b[i]);
	}
	root[0] = upd(1,1,n+1,n+1,n);
	for(int i = 1;i<=n+1;i++){
		int last = root[i-1];
		for(auto u:tmp[i]){
			last = upd(last,1,n+1,u,1);
		}
		last = upd(last,1,n+1,i-1,-get(1,1,n+1,i-1,i-1));
		root[i] = last;
		//cout << root[i] << " " << get(root[i],1,n+1,2,2) << endl;
	} 
	/*
	for(int i = 0;i<n;i++){
		s[0].insert(n+1);
	}
	for(int i = 1;i<=n;i++){
		s[i] = s[i-1];
		for(auto u:tmp[i]){
			s[i].insert(u);
		}
		while(s[i].size() && *s[i].begin() < i){
			s[i].erase(s[i].begin());
		}
	}*/
}
pair<int,int> val[N];
int can(int m, int k[]) {
	map<int,int> mp;
	sort(k,k+m);	
	long long sum = 0;
	for(int i = 0;i<m;i++){
		sum += k[i];
		mp[k[i]]++;
	}
	if(sum > n)return 0;
	vector<pair<int,int>> v;
	for(auto u:mp){
		v.push_back(u);
	}
	vector<int> st;
	for(int x = 0;x<v.size();x++){
		int needed = v[x].first * v[x].second;
		int del = v[x].first-1;
		int tot = 0;
		for(int i = v[x].first;i<=n+1;i++){
			int nwcount = get(root[v[x].first],1,n+1,i,i);
			//cout << root[v[x].first] << "q" << nwcount << " "  << i << endl;
			int delcount = 0;
			for(auto u:st){
				if(val[u].first + 1 < i)continue;
				int nwdel = get(root[u],1,n+1,i,i);
				if(val[u].first + 1 == i){
					delcount += val[u].second;
					continue;
				}
				else delcount = nwdel;
			}
			nwcount -= delcount;
			if(tot + nwcount <= needed){
				del++;
				tot += nwcount;
			}
			else break;
		}
		//cout << del << " " << tot << endl;
		val[v[x].first] = {del,needed-tot};
		while(st.size() && val[st.back()].first < val[v[x].first].first){
			st.pop_back();
		}
		st.push_back(v[x].first);
		if(val[v[x].first].first == n && val[v[x].first].second)return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int x = 0;x<v.size();x++){
      |                ~^~~~~~~~~

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