Submission #590160

#	Time	Username	Problem	Language	Result	Execution time	Memory
590160		FatihSolak	Teams (IOI15_teams)	C++17	100 / 100	3196 ms	287276 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define N 500005
#define K 100
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 tot = 0;
		int sum = 0;
		int samesum = 0;
		int oldsum = 0;
		int rp = -1;
		int l = v[x].first-1,r = n;
		bool ok = 0;
		for(int i = st.size()-1;i>=0;i--){
			if(val[st[i]].first + 1 < v[x].first)continue;
			samesum += val[st[i]].second; 
			if(rp == -1)rp = st[i];
			if(i && val[st[i-1]].first == val[st[i]].first){
				continue;
			}
			if(get(root[v[x].first],1,n+1,v[x].first,val[st[i]].first)-   (sum + get(root[rp],1,n+1,l+1,val[st[i]].first) + oldsum) > needed){
				int ll = l, rr = val[st[i]].first-1;
				while(ll < rr){
					int mm = (ll + rr + 1)/2;
					if(get(root[v[x].first],1,n+1,v[x].first,mm)-   (sum + get(root[rp],1,n+1,l+1,mm) + oldsum) > needed){
						rr = mm-1;
					}
					else ll = mm;
				}
				l = ll;
				ok = 1;
				break;
			}
			sum += oldsum;
			sum += get(root[rp],1,n+1,l+1,val[st[i]].first);
			l = val[st[i]].first;
			oldsum = samesum;
			samesum = 0;
			rp = -1;
		}
		if(!ok){
			int ll = l, rr = n;
			while(ll < rr){
				int mm = (ll + rr + 1)/2;
				if(get(root[v[x].first],1,n+1,v[x].first,mm)-   sum - oldsum> needed){
					rr = mm-1;
				}
				else ll = mm;
			}
			l = ll;
		}
		/*
		while(l < r){
			int m = (l + r + 1)/2;
			int 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;
		}*/
		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 <= l)
				tot -= val[st[i]].second;
			int p1 = min(val[st[i]].first,l);
			int p2 = v[x].first;
			if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
			if(p1 >= p2)
				tot -= get(root[st[i]],1,n+1,p2,p1);
		}
		val[v[x].first] = {l,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:79:7: warning: declaration of 'sum' shadows a previous local [-Wshadow]
   79 |   int sum = 0;
      |       ^~~
teams.cpp:65:12: note: shadowed declaration is here
   65 |  long long sum = 0;
      |            ^~~
teams.cpp:85:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   85 |   for(int i = st.size()-1;i>=0;i--){
      |               ~~~~~~~~~^~
teams.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |   for(int i = 0;i<st.size();i++){
      |                 ~^~~~~~~~~~
teams.cpp:149:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
      |       ~~~~^~~~~~~~~~~~
teams.cpp:83:24: warning: unused variable 'r' [-Wunused-variable]
   83 |   int l = v[x].first-1,r = n;
      |                        ^

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