Submission #289704

#	Time	Username	Problem	Language	Result	Execution time	Memory
289704		amoo_safar	Teams (IOI15_teams)	C++17	100 / 100	1487 ms	155072 KiB

teams

#include "teams.h"

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int N = 5e5 + 10;
const int Log = 20;
const int Sq = 400;

int n, Rs[N];
vector<int> Bs, Qu[N];

int val[N * Log], Lc[N * Log], Rc[N * Log], la;
int rt[N];

void Add(int id, int g, int idx, int L, int R){
	val[id] = val[g] + 1;
	if(L + 1 == R){
		return ;
	}

	Lc[id] = Lc[g];
	Rc[id] = Rc[g];

	int mid = (L + R) >> 1;
	if(idx < mid){
		Lc[id] = ++ la;
		//val[la] = val[Lc[g]];
		Add(Lc[id], Lc[g], idx, L, mid);
	} else {
		Rc[id] = ++ la;
		//val[la] = val[Rc[g]];
		Add(Rc[id], Rc[g], idx, mid, R);
	}
	//val[id] = val[Lc[id]] + val[Rc[id]];
}
int Get(int id, int l, int r, int L, int R){
	if(r <= L || R <= l) return 0;
	if(l <= L && R <= r) return val[id];
	int mid = (L + R) >> 1;
	return Get(Lc[id], l, r, L, mid) + Get(Rc[id], l, r, mid, R);
}

int Rect(int x1, int y1, int x2, int y2){
	if(y2 < y1 || x2 < x1) return 0;
	return Get(rt[x2], y1, y2 + 1, 0, N) - Get(rt[x1 - 1], y1, y2 + 1, 0, N);
}

int BinarySearch(int idL, int idR, int cnt, int L, int R){
	if(L + 1 == R) return L;
	int mid = (L + R) >> 1;

	if(val[Lc[idR]] - val[Lc[idL]] >= cnt)
		return BinarySearch(Lc[idL], Lc[idR], cnt, L, mid);
	cnt -= val[Lc[idR]] - val[Lc[idL]];
	return BinarySearch(Rc[idL], Rc[idR], cnt, mid, R);
}


void init(int32_t _n, int32_t A[], int32_t B[]) {
	memset(val, 0, sizeof val);
	memset(Lc, 0, sizeof Rc);
	memset(Rc, 0, sizeof Lc);
	
	n = _n;
	vector<int> I(n);
	iota(all(I), 0);
	sort(all(I), [&](int i, int j){
		return B[i] < B[j];
	});
	for(int i = 0; i < n; i++) Rs[I[i]] = i;
	//for(int i = 0; i < n; i++) L[i] = A[i];
	for(int i = 0; i < n; i++)
		Bs.pb(B[I[i]]);

	for(int i = 0; i < n; i++) Qu[A[i]].pb(Rs[i]);

	int nw = 1, G; la = 1;
	val[1] = 0, Rc[1] = 0, Lc[1] = 0;

	for(int i = 1; i <= n; i++){
		sort(all(Qu[i]));
		for(int j = 0; j + 1 < (int) Qu[i].size(); j++) assert(Qu[i][j] != Qu[i][j + 1]);
		for(auto y : Qu[i]){
			G = nw;
			nw = la + 1; la ++;
			Add(nw, G, y, 0, N);
		}
		rt[i] = nw;	
	}
}


int yk[N];
int32_t can(int32_t m, int32_t K[]){
	sort(K, K + m);
	for(int i = 0; i < m; i++)
		yk[i] = lower_bound(all(Bs), K[i]) - Bs.begin();

	vector<pii> st;
	pii tmp, tmp2;
	int req, y, res;

	st.pb(pii(0, N - 1));
	for(int gp = 0; gp < m; gp++){
		req = K[gp]; y = yk[gp];
		//if(gp == 0) cerr << y << '\n';
		while(gp + 1 < m && K[gp + 1] == K[gp]){
			gp ++;
			req += K[gp];
		}

		while(st.size() > 1){
			if(st.back().S < y){
				st.pop_back();
				continue;
			}
			res = Rect(st.back().F + 1, y, K[gp], st.back().S);
			if(res >= req)
				break;
			tmp = st.back(); st.pop_back();
			//req += Rect(st.back().F + 1, y, tmp.F, tmp.S);
			req -= res;
			y = tmp.S + 1;
		}
		//if(req > Rect(st.back().F + 1, y, K[gp], N - 1))
		//	return 0;
		req += Rect(st.back().F + 1, 0, K[gp], y - 1);
		/*int Lb = y - 1, Rb = N - 1, mid;
		while(Lb + 1 < Rb){
			mid = (Lb + Rb) >> 1;
			if(req > Rect(st.back().F + 1, 0, K[gp], mid)) Lb = mid;
			else Rb = mid;
		}*/
		int Rb = BinarySearch(rt[st.back().F], rt[K[gp]], req, 0, N);
		if(Rb == N - 1) return 0;
		st.pb({K[gp], Rb});
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:108:38: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  108 |   yk[i] = lower_bound(all(Bs), K[i]) - Bs.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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