Submission #1089392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089392		PanosPask	Teams (IOI15_teams)	C++14	0 / 100	4066 ms	373180 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

typedef pair<int, int> pi;

struct SegTree {
	struct Node {
		Node *l, *r;

		int v;

		Node(int a) {
			v = a;
			l = nullptr;
			r = nullptr;
		}
		Node(Node* a, Node* b) {
			v = 0;
			l = a;
			r = b;
		}
	};

	int size;
	vector<Node*> roots;
	Node* null;

	void init(int N) {
		size = 1;
		while (size < N) {
			size *= 2;
		}

		null = new Node(0);
		null->l = null;
		null->r = null;

		roots.push_back(null);
	}

	Node* add(int i, int v, Node* x, int lx, int rx) {
		x = new Node(x->l, x->r);
		x->v = x->l->v + x->r->v;

		if (lx == rx - 1) {
			x->v += v;
			return x;
		}

		int mid = (lx + rx) / 2;
		if (i < mid) {
			x->l = add(i, v, x->l, lx, mid);
		}
		else {
			x->r = add(i, v, x->r, mid, rx);
		}

		x->v = x->l->v + x->r->v;

		return x;
	}
	int add(int i, int v) {
		roots.push_back(add(i, v, roots.back(), 0, size));
		return roots.size() - 1;
	}

	int sum(int l, int r, Node* x, int lx, int rx) {
		if (l >= rx || lx >= r) {
			return 0;
		}
		else if (l <= lx && rx <= r) {
			return x->v;
		}

		int mid = (lx + rx) / 2;
		return sum(l, r, x->l, lx, mid) + sum(l, r, x->r, mid, rx);
	}
	int sum(int l, int r, int root) {
		return sum(l, r, roots[root], 0, size);
	}

	int kth(int k, Node* x, int lx, int rx) {
		if (x->v < k) {
			return -1;
		}
		if (lx == rx - 1) {
			return lx;
		}

		int mid = (lx + rx) / 2;
		int ans = kth(k, x->l, lx, mid);
		if (ans == -1) {
			ans = kth(k - x->l->v, x->r, mid, rx);
		}

		return ans;
	}

	// Returns the position of the kth 1 if we start counting from pos
	int kth_after(int k, int pos, int root) {
		return kth(k + sum(0, pos, root), roots[root], 0, size);
	}
};

struct Student {
	int a, b;
	int id;
};

struct Event {
	int v;
	bool end;
	int id;
};

bool operator < (Event a, Event b)
{
	if (a.v == b.v) {
		return a.end < b.end;
	}
	return a.v < b.v;
}

int N;
SegTree st;

// Position of each student in the segment tree
vector<Event> events;
vector<Event> insertions;
vector<int> pos;
vector<int> root_id;

void init(int n, int A[], int B[])
{
	N = n;

	pos.resize(N);
	root_id.resize(N);
	st.init(2 * N);

	for (int i = 0; i < N; i++) {
		events.push_back({A[i], false, i});
		events.push_back({B[i], true, i});
		insertions.push_back({A[i], false, i});
	}
	sort(events.begin(), events.end());
	sort(insertions.begin(), insertions.end());

	for (int i = 0; i < 2 * N; i++) {
		if (events[i].end) {
			pos[events[i].id] = i;
		}
	}
	for (int i = 0; i < 2 * N; i++) {
		if (!events[i].end) {
			root_id[events[i].id] = st.add(pos[events[i].id], 1);
		}
	}
}

int can(int M, int K[])
{
	sort(K, K + M);

	vector<int> prv(M);
	vector<int> p_idx(M);
	for (int i = 0; i < M; i++) {
		int start = upper_bound(insertions.begin(), insertions.end(), Event{K[i], false, -1}) - insertions.begin() - 1;
		start = upper_bound(events.begin(), events.end(), insertions[start]) - events.begin() - 1;
		int root = root_id[events[start].id];

		int remove = 0;
		int upto = start;
		for (int j = i - 1; j >= 0; j--) {
			remove += st.sum(upto, prv[j] + 1, p_idx[j]);
			upto = max(upto, prv[j] + 1);
		}

		int res = st.kth_after(K[i] + remove, start, root);
		if (res == -1) {
			return 0;
		}

		prv[i] = res;
		p_idx[i] = root;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int SegTree::add(int, int)':
teams.cpp:66:23: warning: conversion from 'std::vector<SegTree::Node*>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   66 |   return roots.size() - 1;
      |          ~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:170:110: warning: conversion from '__gnu_cxx::__normal_iterator<Event*, std::vector<Event> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  170 |   int start = upper_bound(insertions.begin(), insertions.end(), Event{K[i], false, -1}) - insertions.begin() - 1;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:171:89: warning: conversion from '__gnu_cxx::__normal_iterator<Event*, std::vector<Event> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  171 |   start = upper_bound(events.begin(), events.end(), insertions[start]) - events.begin() - 1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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