Submission #590085

#	Time	Username	Problem	Language	Result	Execution time	Memory
590085		FatihSolak	Teams (IOI15_teams)	C++17	0 / 100	1495 ms	281176 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;
	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;
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;
	} 
}
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;
		int l = v[x].first-1,r = n;
		while(l < r){
			int m = (l + r + 1)/2;
			long long now = get(root[v[x].first],1,n+1,v[x].first,m);
			for(int i = 0;i<st.size();i++){
				if(val[st[i]].first + 1 < v[x].first)break;
				if(val[st[i]].first + 1 <= m)
					now -= val[st[i]].second;
				int p1 = min(val[st[i]].first,m);
				int p2 = v[x].first;
				if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
				if(p1 >= p2)
					now -= get(root[st[i]],1,n+1,p2,p1);
			}
			if(now <= needed){
				l = m;
			}
			else r = m-1;
		}
		del = l;
		tot = get(root[v[x].first],1,n+1,v[x].first,l);
		for(int i = 0;i<st.size();i++){
			if(val[st[i]].first + 1< v[x].first)break;
			if(val[st[i]].first + 1 <= m)
				del -= val[st[i]].second;
			int p1 = min(val[st[i]].first,m);
			int p2 = v[x].first;
			if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
			if(p1 >= p2)
				del -= get(root[st[i]],1,n+1,p2,p1);
		}
		// tot = 0;
		// del = v[x].first -1;
		// 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;
		// 	for(int j = 0;j<st.size();j++){
		// 		if(val[st[j]].first + 1 < i)break;
		// 		if(val[st[j]].first + 1 == i){
		// 			nwcount -= val[st[j]].second;
		// 		}
		// 		else if(j+1 == st.size() || val[st[j+1]].first < i) nwcount -= get(root[st[j]],1,n+1,i,i);
		// 	}
		// 	if(tot + nwcount <= needed){
		// 		del++;
		// 		tot += nwcount;
		// 	}
		// 	else break;
		// }
		assert(del == l);
		//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:76: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]
   76 |  for(int x = 0;x<v.size();x++){
      |                ~^~~~~~~~~
teams.cpp:82:8: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   82 |    int m = (l + r + 1)/2;
      |        ^
teams.cpp:62:13: note: shadowed declaration is here
   62 | int can(int m, int k[]) {
      |         ~~~~^
teams.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int i = 0;i<st.size();i++){
      |                  ~^~~~~~~~~~
teams.cpp:90:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
      |        ~~~~^~~~~~~~~~~~
teams.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i = 0;i<st.size();i++){
      |                 ~^~~~~~~~~~
teams.cpp:107:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
      |       ~~~~^~~~~~~~~~~~

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