Submission #1078562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078562		42kangaroo	Teams (IOI15_teams)	C++17	77 / 100	4019 ms	367456 KiB

teams

//
// Created by 42kangaroo on 26/08/2024.
//
#pragma GCC optimize("Ofast,inline")
#include "bits/stdc++.h"
#include "teams.h"

using namespace std;

struct Node {
	int l, r, lr, rr, su;
};

struct StV {
	int l, r, nu, root;
};

struct FenTe {
	vector<int> a;

	void inc(int k, int v) {
		for (int i = k + 1; i < a.size(); i += i & -i) {
			a[i] += v;
		}
	}

	int get(int k) {
		int res = 0;
		for (int i = k + 1; i > 0; i -= i & -i) {
			res += a[i];
		}
		return res;
	}
};

int n;
FenTe fe;

struct PerSegTe {
	vector<Node> a;

	int build(int l, int r) {
		int ind = a.size();
		a.push_back({-1, -1, l, r, 0});
		if (l + 1 < r) {
			int m = (l + r) / 2;
			a[ind].l = build(l, m);
			a[ind].r = build(m, r);
		}
		return ind;
	}

	int add(int i, int k, int v) {
		if (a[i].rr <= k || a[i].lr > k) return i;
		int ind = a.size();
		a.push_back(a[i]);
		if (a[i].r == -1) {
			a[ind].su += v;
			return ind;
		}
		a[ind].l = add(a[i].l, k, v);
		a[ind].r = add(a[i].r, k, v);
		a[ind].su += v;
		return ind;
	}

	int get(int i, int l, int r) {
		if (a[i].rr <= l || r <= a[i].lr) return 0;
		if (l <= a[i].lr && a[i].rr <= r) return a[i].su;
		return get(a[i].l, l, r) + get(a[i].r, l, r);
	}

	int miI(int i, int pos, vector<StV> &ros, int nu) {
		if (ros.empty()) {
			int l = pos - 1, r = 2 * n + 1;
			while (l + 1 < r) {
				int m = (l + r) / 2;
				int act = get(i, pos, m + 1);
				if (act >= nu) r = m;
				else l = m;
			}
			return r;
		}
		int ot = get(ros.back().root, 0, pos);
		int l = pos - 1, r = 2 * n + 1;
		while (l + 1 < r) {
			int m = (l + r) / 2;
			int act = get(i, pos, m + 1);
			act += ot;
			act -= fe.get(m + 1);
			if (act >= nu) r = m;
			else l = m;
		}
		if (r == 2*n + 1) return r;
		int ll = -1, rr = ros.size() - 1;
		while (ll + 1 < rr) {
			int m = (ll + rr) / 2;
			if (ros[m].l <= l) rr = m;
			else ll = m;
		}
		int ind = rr;
		ll = max(ros[ind].l - 1, pos - 1), rr = ros[ind].r;
		if (ind == 0) rr = 2*n + 1;
		ot -= fe.get(ros[ind].l - 1);
		while (ll + 1 < rr) {
			int m = (ll + rr) / 2;
			int act = get(i, pos, m + 1);
			act += ot;
			act -= get(ros[ind].root, ros[ind].l, min(ros[ind].r, m) + 1);
			if (act >= nu) rr = m;
			else ll = m;
		}
		return rr;
	}
};

struct Ev {
	int t, p, v;
};

bool operator<(const Ev &l, const Ev &r) {
	return tie(l.t, l.v) < tie(r.t, r.v);
}

PerSegTe se;
vector<pair<int, int>> ros;
vector<int> bCC;


void init(int N, int A[], int B[]) {
	vector<int> a(A, A + N), b(B, B + N);
	n = N;
	se.a.clear();
	auto bC = b;
	bC.insert(bC.end(), a.begin(), a.end());
	std::sort(bC.begin(), bC.end());
	bCC = bC;
	vector<int> o(a.size());
	std::iota(o.begin(), o.end(),0);
	std::sort(o.begin(), o.end(), [&](int l, int r){return a[l] < a[r];});
	for (int i = 0; i < a.size(); ++i) {
		int ind = std::lower_bound(bC.begin(), bC.end(), a[o[i]]) - bC.begin();
		a[o[i]] = ind;
		bC[ind]--;
	}
	for (int i = 0; i < b.size(); ++i) {
		int ind = std::lower_bound(bC.begin(), bC.end(), b[o[i]]) - bC.begin();
		b[o[i]] = ind;
		bC[ind]--;
	}
	se.build(0, 2 * N + 1);
	vector<Ev> evs;
	for (int i = 0; i < N; ++i) {
		evs.push_back({a[i], b[i], 1});
	}
	std::sort(evs.begin(), evs.end());
	int laR = 0;
	ros.clear();
	for (int i = 0; i < evs.size(); ++i) {
		laR = se.add(laR, evs[i].p, evs[i].v);
		ros.push_back({evs[i].t, laR});
	}
	std::sort(ros.begin(), ros.end());
	fe.a = vector<int>(2 * n + 3, 0);
}


int can(int M, int K[]) {
	vector<int> k(K, K + M);
	if (accumulate(k.begin(), k.end(), 0ll) > n) return 0;
	map<int, int> vals;
	for (int i = 0; i < k.size(); ++i) {
		vals[k[i]] += k[i];
	}
	vector<StV> laO;
	for (auto [whi, nu]: vals) {
		int whiP = std::lower_bound(bCC.begin(), bCC.end(), whi) - bCC.begin();
		int qW = (std::upper_bound(bCC.begin(), bCC.end(), whi) - bCC.begin()) - 1;
		int whiN = (std::upper_bound(ros.begin(), ros.end(), make_pair(qW, (int) 1e9)) - ros.begin()) - 1;
		if (whiN < 0 || qW < 0) {
			while (!laO.empty()) {
				fe.inc(laO.back().l, -laO.back().nu);
				laO.pop_back();
			}
			return 0;
		}
		while (!laO.empty() && laO.back().r < whiP) {
			fe.inc(laO.back().l, -laO.back().nu);
			laO.pop_back();
		}
		if (!laO.empty()) {
			fe.inc(laO.back().l, -laO.back().nu);
			laO.back().l = 0;
			laO.back().nu = se.get(laO.back().root, laO.back().l, laO.back().r + 1);
			fe.inc(laO.back().l, laO.back().nu);
		}
		int miI = se.miI(ros[whiN].second, whiP, laO, nu);
		if (miI > 2 * n) {
			while (!laO.empty()) {
				fe.inc(laO.back().l, -laO.back().nu);
				laO.pop_back();
			}
			return 0;
		}
		while (!laO.empty() && laO.back().r <= miI) {
			fe.inc(laO.back().l, -laO.back().nu);
			laO.pop_back();
		}
		if (!laO.empty()) {
			fe.inc(laO.back().l, -laO.back().nu);
			laO.back().l = miI;
			laO.back().nu = se.get(laO.back().root, laO.back().l, laO.back().r + 1);
			fe.inc(laO.back().l, laO.back().nu);
		}
		laO.push_back({0, miI, se.get(ros[whiN].second, 0, miI + 1), ros[whiN].second});
		fe.inc(0, laO.back().nu);
	}
	while (!laO.empty()) {
		fe.inc(laO.back().l, -laO.back().nu);
		laO.pop_back();
	}
	return 1;
}

vector<vector<int>> evs;

void init2(int N, int A[], int B[]) {
	vector<int> a(A, A + N);
	vector<int> b(B, B + N);
	evs = vector<vector<int>>(N + 1);
	for (int i = 0; i < N; ++i) {
		evs[a[i]].push_back(b[i]);
	}
}

int can2(int M, int K[]) {
	vector<int> k(K, K + M);
	vector<long long> nuI(evs.size());
	for (int i = 0; i < M; ++i) {
		nuI[k[i]] += k[i];
	}
	multiset<int> in;
	for (int i = 0; i < evs.size(); ++i) {
		while (!in.empty() && *in.begin() < i) in.erase(in.begin());
		for (auto e: evs[i]) {
			in.insert(e);
		}
		for (int j = 0; j < nuI[i]; ++j) {
			if (in.empty()) return 0;
			in.erase(in.begin());
		}
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'void FenTe::inc(int, int)':
teams.cpp:22:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (int i = k + 1; i < a.size(); i += i & -i) {
      |                       ~~^~~~~~~~~~
teams.cpp: In member function 'int PerSegTe::build(int, int)':
teams.cpp:43:19: warning: conversion from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   43 |   int ind = a.size();
      |             ~~~~~~^~
teams.cpp: In member function 'int PerSegTe::add(int, int, int)':
teams.cpp:55:19: warning: conversion from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   55 |   int ind = a.size();
      |             ~~~~~~^~
teams.cpp: In member function 'int PerSegTe::miI(int, int, std::vector<StV>&, int)':
teams.cpp:95:32: warning: conversion from 'std::vector<StV>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   95 |   int ll = -1, rr = ros.size() - 1;
      |                     ~~~~~~~~~~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:141:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for (int i = 0; i < a.size(); ++i) {
      |                  ~~^~~~~~~~~~
teams.cpp:142:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  142 |   int ind = std::lower_bound(bC.begin(), bC.end(), a[o[i]]) - bC.begin();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |  for (int i = 0; i < b.size(); ++i) {
      |                  ~~^~~~~~~~~~
teams.cpp:147:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  147 |   int ind = std::lower_bound(bC.begin(), bC.end(), b[o[i]]) - bC.begin();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp:159:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |  for (int i = 0; i < evs.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:172:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |  for (int i = 0; i < k.size(); ++i) {
      |                  ~~^~~~~~~~~~
teams.cpp:177:60: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  177 |   int whiP = std::lower_bound(bCC.begin(), bCC.end(), whi) - bCC.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:178:74: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  178 |   int qW = (std::upper_bound(bCC.begin(), bCC.end(), whi) - bCC.begin()) - 1;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:179:97: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  179 |   int whiN = (std::upper_bound(ros.begin(), ros.end(), make_pair(qW, (int) 1e9)) - ros.begin()) - 1;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can2(int, int*)':
teams.cpp:243:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |  for (int i = 0; i < evs.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

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