Submission #56230

#	Time	Username	Problem	Language	Result	Execution time	Memory
56230		aome	Teams (IOI15_teams)	C++17	100 / 100	2653 ms	240388 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 5000005;
const int M = 2005;

int n;
int ver[N];
int sum[M][M];
int g[M], h[M], f[M][M];
vector< pair<int, int> > seg;

struct SegmentTree {
	struct Node {
		int cnt, l, r;
	};

	int num;
	Node T[20 * N];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (l == r) return;
		T[i].l = ++num;
		build(T[i].l, l, mid);
		T[i].r = ++num;
		build(T[i].r, mid + 1, r);		
	}

	void upd(int i, int j, int l, int r, int p) {
		T[j].cnt = T[i].cnt + 1;
		if (l == r) return;
		if (mid >= p) {
			T[j].l = ++num, T[j].r = T[i].r;
			upd(T[i].l, T[j].l, l, mid, p);
		}
		else {
			T[j].l = T[i].l, T[j].r = ++num;
			upd(T[i].r, T[j].r, mid + 1, r, p);
		}
	}

	int get(int i, int l, int r, int L, int R) {
		if (l > R || L > r) return 0;
		if (L <= l && r <= R) return T[i].cnt;
		return get(T[i].l, l, mid, L, R) + get(T[i].r, mid + 1, r, L, R);
	}

	#undef mid
} IT;

void init(int _n, int A[], int B[]) {
	n = _n;
	for (int i = 0; i < n; ++i) {
		seg.push_back({A[i], B[i]});
	}
	sort(seg.begin(), seg.end());
	IT.build(0, 1, n);
	for (int i = 0; i < n; ++i) {
		ver[i + 1] = ++IT.num;
		if (seg[i].first < M) g[seg[i].first] = i;
		IT.upd(ver[i], ver[i + 1], 1, n, seg[i].second);
	}
	for (int i = 0; i < n; ++i) {
		int x = seg[i].first;
		int y = seg[i].second;
		if (y < M) h[y]++;
		if (x < M && g[x] == i) {
			for (int j = x; j < M; ++j) {
				sum[x][j] = sum[x][j - 1] + h[j];
			}
		}
	}
}

int can(int m, int K[]) {
	// cout << "#query\n";
	sort(K, K + m);
	vector< pair<int, int> > vec;
	for (int i = 0; i < m; ++i) {
		int j = i;
		while (j < m && K[j] == K[i]) j++;
		vec.push_back({K[i], j - i}), i = j - 1;
	}
	int sz = vec.size();
	for (int i = 0; i < sz; ++i) {
		h[i] = 0;
		g[i] = lower_bound(seg.begin(), seg.end(), make_pair(vec[i].first + 1, 0)) - seg.begin();
	}
	for (int i = 0; i < sz; ++i) {
		for (int j = i; j < (sz - 1); ++j) {
			int l = vec[j].first, r = vec[j + 1].first - 1;
			if (r < M) {
				int x = 0;
				if (g[i]) x = seg[g[i] - 1].first;
				f[i][j] = sum[x][r] - sum[x][l - 1];
			}
			else {
				f[i][j] = IT.get(ver[g[i]], 1, n, l, r);
			}
		}
		f[i][sz - 1] = IT.get(ver[g[i]], 1, n, vec[sz - 1].first, n);
		// cout << g[i] << '\n';
		// for (int j = i; j < sz; ++j) cout << f[i][j] << ' ';
		// cout << '\n';
	}
	bool fail = 0;
	for (int i = 0; i < sz; ++i) {
		int need = vec[i].second * vec[i].first;
		for (int j = i; j < sz; ++j) {
			f[i][j] -= h[j];
			int tmp = min(need, f[i][j]);
			h[j] += tmp, need -= tmp;
		}
		if (need) fail = 1;
	}
	return !fail;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:89:19: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int sz = vec.size();
           ~~~~~~~~^~
teams.cpp:92:78: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   g[i] = lower_bound(seg.begin(), seg.end(), make_pair(vec[i].first + 1, 0)) - seg.begin();
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

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