Submission #329733

#	Time	Username	Problem	Language	Result	Execution time	Memory
329733		figter001	Teams (IOI15_teams)	C++17	0 / 100	1045 ms	193136 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(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=2;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;
	vector<int> k;
	int id = 0;
	for(int i=0;i<M;i++){
		int hv = get(head[lst],1,n,lst,K[i] - 1);
		// cerr << hv << '\n';
		while(id < k.size()){
			if(hv >= k[id]){
				hv-=k[id];
				ex -= k[id];
				id++;
			}else{
				k[id] -= hv;
				ex -= hv;
				break;
			}
		}

		ex += K[i];
		// cerr << K[i] << ' ' << ex << ' ' << get(head[K[i]],1,n,K[i] , n) << '\n';
		if(get(head[K[i]],1,n,K[i] , n) < ex)return 0;

		k.push_back(K[i]);
		lst = head[K[i]];
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:89:61: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |   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:89:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |   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:89:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |   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:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   lst = head[s[i].first];
      |         ~~~~~~~~~~~~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  107 |   int hv = get(head[lst],1,n,lst,K[i] - 1);
      |                ~~~~~~~~^
teams.cpp:107:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  107 |   int hv = get(head[lst],1,n,lst,K[i] - 1);
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:109:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   while(id < k.size()){
      |         ~~~^~~~~~~~~~
teams.cpp:123:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |   if(get(head[K[i]],1,n,K[i] , n) < ex)return 0;
      |          ~~~~~~~~~^
teams.cpp:126:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  126 |   lst = head[K[i]];
      |         ~~~~~~~~~^

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