Submission #590037

#	Time	Username	Problem	Language	Result	Execution time	Memory
590037		FatihSolak	Teams (IOI15_teams)	C++17	0 / 100	1526 ms	274100 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(i + 1 != st.size() && st[i+1] > m)continue;
				if(st[i] < v[x].first)break;
				if(st[i] <= m)
					now -= v[st[i]].second;
				int ps = v[x].first;
				if(i+1 != st.size())ps = st[i+1];
				now -= (st[i] - ps) * get(root[st[i]],1,n+1,v[x].first,m);
			}
			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(i + 1 != st.size() && st[i+1] > l)continue;
			if(st[i] < v[x].first)break;
			if(st[i] <= l)
				tot -= v[i].second;
			int ps = v[x].first;
			if(i+1 != st.size())ps = st[i+1];
			tot -= (st[i] - ps) * get(root[st[i]],1,n+1,v[x].first,l);
		}
		/*
		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;
			int delcount = 0;
			for(auto u:st){
				if(val[u].first + 1 < i)break;
				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: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:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     if(i + 1 != st.size() && st[i+1] > m)continue;
      |        ~~~~~~^~~~~~~~~~~~
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())ps = st[i+1];
      |        ~~~~^~~~~~~~~~~~
teams.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i = 0;i<st.size();i++){
      |                 ~^~~~~~~~~~
teams.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    if(i + 1 != st.size() && st[i+1] > l)continue;
      |       ~~~~~~^~~~~~~~~~~~
teams.cpp:106:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    if(i+1 != st.size())ps = st[i+1];
      |       ~~~~^~~~~~~~~~~~

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