Submission #329747

#	Time	Username	Problem	Language	Result	Execution time	Memory
329747		figter001	Teams (IOI15_teams)	C++17	0 / 100	2407 ms	191328 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int nax = 5e5 + 100;

struct node{
	int l,r;
	ll sum;
	node(){
		l = r = -1;
		sum = 0;
	}	
}seg[22*nax];
 
ll head[nax];
int T;

void update(int n,int s,int e,int at,int val,int old){
	if(s == e){
		// cerr << n << ' ' << old << ' ' << seg[old].sum << '\n';
		seg[n].sum += seg[old].sum + val;
		return;
	}
	if((s+e)/2 < at)seg[n].l = seg[old].l;
	else{
		seg[n].l = ++T;
		update(seg[n].l,s,(s+e)/2,at,val,seg[old].l);
	}
	if((s+e)/2+1 > at)seg[n].r = seg[old].r;
	else{
		seg[n].r = ++T;
		update(seg[n].r,(s+e)/2+1,e,at,val,seg[old].r);
	}
	seg[n].sum = seg[ seg[n].l ].sum + seg[ seg[n].r ].sum;
	// cerr << seg[n].sum << ' ' << s << ' ' << e << '\n';
}
 
ll get(int n,int s,int e,int l,int r){
	if(n <= 0)return 0;
	// assert(n >0);
	if(s > r || e < l || l > r)return 0;
	if(s >= l && e <= r)return seg[n].sum;
	return get( seg[n].l , s , (s+e)/2 , l , r ) + get( seg[n].r , (s+e)/2+1 , e , l , r);
}

// int main(){
// 	int cur = 1;
// 	head[cur] = ++T;
// 	build(head[1],1,n);
// 	for(int i=0;i<q;i++){
// 		int t,k;
// 		cin>>t>>k;
// 		if(t == 1){//update
// 			int at,val;
// 			cin>>at>>val;
// 			int old = head[k];
// 			head[k] = ++T;
// 			update(head[k],1,n,at,val,old);
// 		}else if(t == 2){//sum
// 			int l,r;
// 			cin>>l>>r;
// 			cout << get(head[k],1,n,l,r) << endl;
// 		}else if(t == 3){//make new
// 			cur++;
// 			head[cur] = head[k];
// 		}
// 	}
// }


vector<pair<int,int>> s;
int n;

void init(int N, int A[], int B[]) {
	n = N;
	for(int i=0;i<n;i++)s.push_back({A[i], B[i]});
	sort(all(s));
	head[0] = ++T;
	int lst = T;
	for(int i=0;i<n;i++){
		head[s[i].first] = ++T;
		update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
		// cerr << ' ' << head[s[i].first] << ' ' << lst << ' ' << get(head[s[i].first],1,n,1,n) << '\n';
		lst = head[s[i].first];
	}
	for(int i=1;i<=n;i++){
		if(head[i] == 0)
			head[i] = head[i-1];
	}
}

int can(int M, int K[]) {
	// return 0;
	sort(K,K+M);
	int ex = 0;
	int lst = 0;
	multiset<pair<int,int>> k;
	int id = 0;
	for(int i=0;i<M;i++){
		while(k.size() && k.begin()->first < K[i]){
			ex -= k.begin()->second;
			k.erase(k.begin());
		}
		// cerr << K[i] << ' ' << ex << ' ' << get(head[K[i]],1,n,K[i] , n) << '\n';
		ex += K[i];
		if(get(head[K[i]],1,n,K[i] , n) < ex){
			// cerr << 0 << ' ';
			return 0;
		}
		int lo=K[i],hi = n,to=n;
		while(lo <= hi){
			int md = (lo + hi)/2;
			if(get(head[K[i]] , 1 , n , K[i] , md) >= ex){
				hi = md-1;
				to = md;
			}else{
				lo = md + 1;
			}
		}

		k.insert({to , K[i]});

		// if(k[id] != K[i])return 0;
	}
	// cerr << 1 << ' ';
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:91:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |                                                     ~~~~~~~~^
teams.cpp:91:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |          ~~~~~~~~~~~~~~~^
teams.cpp:91:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   update(head[s[i].first] , 1,n,s[i].second,1 + get(head[lst],1,n,s[i].second,s[i].second),lst);
      |                                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:93:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |   lst = head[s[i].first];
      |         ~~~~~~~~~~~~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:115:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |   if(get(head[K[i]],1,n,K[i] , n) < ex){
      |          ~~~~~~~~~^
teams.cpp:122:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |    if(get(head[K[i]] , 1 , n , K[i] , md) >= ex){
      |           ~~~~~~~~~^
teams.cpp:105:6: warning: unused variable 'lst' [-Wunused-variable]
  105 |  int lst = 0;
      |      ^~~
teams.cpp:107:6: warning: unused variable 'id' [-Wunused-variable]
  107 |  int id = 0;
      |      ^~

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