oj.uz

Submission #1089388

# Submission time Handle Problem Language Result Execution time Memory
1089388 2024-09-16T11:19:26 Z PanosPask Teams (IOI15_teams) C++14
0 / 100
 1285 ms 373500 KB 
#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);

	int prv = -1;
	int p_idx = 0;
	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 = st.sum(start, prv + 1, p_idx);

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

		prv = res;
		p_idx = root;
	}

	return 1;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 66812 KB Output is correct
2 Correct 111 ms 66904 KB Output is correct
3 Correct 106 ms 66840 KB Output is correct
4 Correct 110 ms 67332 KB Output is correct
5 Correct 99 ms 66480 KB Output is correct
6 Correct 82 ms 66472 KB Output is correct
7 Incorrect 85 ms 66396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 67552 KB Output is correct
2 Correct 130 ms 67624 KB Output is correct
3 Correct 257 ms 70944 KB Output is correct
4 Correct 128 ms 67328 KB Output is correct
5 Correct 144 ms 67328 KB Output is correct
6 Correct 140 ms 67224 KB Output is correct
7 Incorrect 147 ms 67328 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 366664 KB Output is correct
2 Correct 788 ms 366652 KB Output is correct
3 Correct 1285 ms 373500 KB Output is correct
4 Correct 683 ms 366340 KB Output is correct
5 Correct 605 ms 363892 KB Output is correct
6 Correct 589 ms 363816 KB Output is correct
7 Incorrect 620 ms 363916 KB Output isn't correct
8 Halted 0 ms 0 KB -