Submission #786983

#	Time	Username	Problem	Language	Result	Execution time	Memory
786983		fatemetmhr	Teams (IOI15_teams)	C++17	100 / 100	760 ms	176632 KiB

teams

//  ~ Be Name Khoda ~  //

#include "teams.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnl =  2e7   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const int lg    =  21;
const ll  inf   =  1e18;

int n, newnode = 2, k[maxn5], m, root[maxn5];
vector <int> av[maxn5];

namespace seg{

	int sum[maxnl], chil[maxnl][2];


	void cop(int i, int j){
		sum[i] = sum[j];
		chil[i][0] = chil[j][0];
		chil[i][1] = chil[j][1];
	}

	void add(int l, int r, int id, int v){
		sum[v]++;
		if(r - l == 1)
			return;
		int mid = (l + r) >> 1, v2 = newnode++;
		if(id < mid){
			cop(v2, chil[v][0]);
			chil[v][0] = v2;
			add(l, mid, id, v2);
		}
		else{
			cop(v2, chil[v][1]);
			chil[v][1] = v2;
			add(mid, r, id, v2);
		}
	}

	int get_first(int l, int r, int v1, int v2, int k){
		//cout << "ya get first " << l << ' ' << r << ' ' << v1 << ' ' << v2 << ' ' << k << ' ' << sum[v1] << ' ' << sum[v2] << endl;
		if(r - l == 1)
			return l;
		int mid = (l + r) >> 1;
		if(sum[chil[v2][0]] - sum[chil[v1][0]] >= k)
			return get_first(l, mid, chil[v1][0], chil[v2][0], k);
		k -= sum[chil[v2][0]] - sum[chil[v1][0]];
		return get_first(mid, r, chil[v1][1], chil[v2][1], k);
	}

	int get_sum(int l, int r, int lq, int rq, int v){
		if(rq <= l || r <= lq || v == 0)
			return 0;
		////cout << "while getting sum " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << v << ' ' << sum[v] << endl;
		if(lq <= l && r <= rq)
			return sum[v];
		int mid = (l + r) >> 1;
		return get_sum(l, mid, lq, rq, chil[v][0]) + get_sum(mid, r, lq, rq, chil[v][1]);
	}

	int get(int l1, int r1, int l2, int r2){
		r1--; l1--;
		ll sum = get_sum(0, n, l2, r2, root[r1]);
		////cout << "ok now " << l1 << ' ' << r1 << ' ' << l2 <<  ' ' << r2 << ' ' << sum << ' ' << seg::sum[root[0]] << ' ' << root[0] << endl;
		if(l1 >= 0)
			sum -= get_sum(0, n, l2, r2, root[l1]);
		return sum;
	}

}

struct chtnode{
	int nxt, pre, cons, id;
	bool rem;

	void clear(){
		nxt = -1;
		id = cons = 0;
		rem = false;
	}
} node[maxn5];

namespace cht{

	int ind = 0, cur = 0, st;
	vector <pair<int, int>> todo[maxn5];

	void clear(){
		node[0].clear();
		st = 0;
		ind = 1;
		cur = 0;
		for(int i = 0; i <= m; i++)
			todo[i].clear();
	}


	int get_tim(int a, int b){
		//cout << "hey "  << a << ' ' << b << ' ' << node[a].id << ' ' << node[b].id << endl;
		ll lim = node[a].cons - node[b].cons;
		//cout << node[b].cons << endl;
		a = node[a].id; b = node[b].id;
		//////cout << a << ' ' << root[a] << endl;
		int all = seg::sum[root[b]] - seg::sum[root[a]];
		//cout << a << ' ' << b << ' ' << lim << ' ' << all << endl;
		int ans = seg::get_first(0, n, root[a], root[b], all - lim);
		int pt = upper_bound(k, k + m, ans) - k;
		//cout << "for " << ans << ' ' << pt << endl;
		return max(cur, pt);
	}

	int get_max(int id){
		//cout << "*********** " << id << endl;
		cur = id;
		while(todo[id].size()){
			int x = todo[id].back().fi, y = todo[id].back().se;
			todo[id].pop_back();
			//cout << "removing " << id << ' ' << x << ' ' << y << ' ' << node[x].nxt << endl;
			if(!node[x].rem && !node[y].rem && node[x].nxt == y){
				//cout << "ok " << ' ' << node[x].id << ' ' << node[y].id << endl;
				node[y].rem = true;
				int z = node[y].nxt;
				node[x].nxt = z;
				if(z == -1){
					st = x;
					continue;
				}
				int ti = get_tim(x, z);
				todo[ti].pb({x, z});
			}
		}
		cur++;
		//cout << "here " << st << ' ' << node[st].cons << ' ' << node[st].id << endl;
		return node[st].cons + k[id] - seg::get(node[st].id + 1, k[id] + 1, k[id], n);
	}

	void add(int id, int cons){
		node[ind].clear();
		node[ind].cons = cons;
		node[ind].id = id;
		int ti = get_tim(st, ind);
		//cout << "we have " << ti << endl;
		todo[ti].pb({st, ind});
		node[st].nxt = ind;
		st = ind;
		ind++;
	}

}

void init(int N, int A[], int B[]) {
	seg::sum[0] = seg::chil[0][0] = seg::chil[0][1] = 0;
	n = N;
	for(int i = 0; i < n; i++)
		av[A[i]].pb(B[i]);
	n++;
	int last = 1;
	seg::sum[1] = seg::chil[1][0] = seg::chil[1][1] = 0;
	for(int i = 0; i < n; i++){
		root[i] = newnode++;
		seg::cop(root[i], last);
		last = root[i];
		for(auto u : av[i]){
			root[i] = newnode++;
			seg::cop(root[i], last);
			last = root[i];
			seg::add(0, n, u, root[i]);
		}
		////cout << i << ' ' << newnode << ' ' << root[i] << ' ' << seg::chil[root[i]][0] << ' ' << seg::chil[root[i]][1] << endl;
	}
}

int can(int M, int K[]) {
	m = M;
	for(int i = 0; i < m; i++)
		k[i] = K[i];
	sort(k, k + m);
	cht::clear();
	int ans = 0;
	for(int i = 0; i < m; i++){
		int dp = cht::get_max(i);
		//cout << i << ' ' << k[i] << ' ' << dp << endl;
		ans = max(ans, dp);
		cht::add(k[i], dp);
	}
	return ans <= 0;
}

Compilation message (stderr)

teams.cpp: In function 'int seg::get(int, int, int, int)':
teams.cpp:81:6: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
   81 |   ll sum = get_sum(0, n, l2, r2, root[r1]);
      |      ^~~
teams.cpp:32:6: note: shadowed declaration is here
   32 |  int sum[maxnl], chil[maxnl][2];
      |      ^~~
teams.cpp:85:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   85 |   return sum;
      |          ^~~
teams.cpp: In function 'int cht::get_tim(int, int)':
teams.cpp:124:56: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |   int ans = seg::get_first(0, n, root[a], root[b], all - lim);
      |                                                    ~~~~^~~~~
teams.cpp:125:39: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  125 |   int pt = upper_bound(k, k + m, ans) - k;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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