oj.uz

답안 #828508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828508 2023-08-17T10:37:37 Z Josia 팀들 (IOI15_teams) C++17
100 / 100
 3809 ms 229324 KB 
#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

// #define int int64_t

int n;

struct Query {
	struct seg {
		struct node {
			int val = 0;
			int l = -1;
			int r = -1;
		};
		vector<node> tree = {{0, -1, -1}};

		void build(int v, int rl, int rr) {
			if (rl == rr) return;

			tree[v].l = tree.size();
			tree.push_back(node());
			tree[v].r = tree.size();
			tree.push_back(node());

			int rm = (rl + rr)/2;
			build(tree[v].l, rl, rm);
			build(tree[v].r, rm+1, rr);
		}

		int update(int v, int rl, int rr, int pos, int val) {
			if (rl == rr) {
				int newV = tree.size();

				tree.push_back(tree[v]);

				tree[newV].val = val;
				return newV;
			}
			int rm = (rl + rr)/2;

			int newV = tree.size();

			tree.push_back(tree[v]);

			if (pos <= rm) tree[newV].l = (update(tree[newV].l, rl, rm, pos, val));
			else tree[newV].r = (update(tree[newV].r, rm+1, rr, pos, val));

			tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val;

			return newV;
		}

		int query(int v, int rl, int rr, int ql, int qr) {
			if (ql > qr) return 0;

			if (rl == ql && rr == qr) return tree[v].val;

			int rm = (rl + rr)/2;

			return query(tree[v].l, rl, rm, ql, min(rm, qr)) + query(tree[v].r, rm+1, rr, max(rm+1, ql), qr);
		}
	};
	
	vector<pair<pair<int, int>, pair<int, int>>> rangesWithSortedIndicies;
	vector<pair<int, int>> beginWithIndicies;
	vector<pair<int, int>> endWithIndicies;

	vector<int> startTimes;

	seg tree;

	void initQuery(vector<pair<int, int>> &ranges) {
		rangesWithSortedIndicies.resize(n);
		beginWithIndicies.resize(n);
		endWithIndicies.resize(n);

		for (int i = 0; i<n; i++) {
			rangesWithSortedIndicies[i].first.first = ranges[i].first;
			rangesWithSortedIndicies[i].second.first = ranges[i].second;
		}

		sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());

		for (int i = 0; i<n; i++) {
			rangesWithSortedIndicies[i].first.second = i;
			swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second);

			beginWithIndicies[i] = rangesWithSortedIndicies[i].second;
		}

		sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());

		for (int i = 0; i<n; i++) {
			rangesWithSortedIndicies[i].first.second = i;
			swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second);

			endWithIndicies[i] = rangesWithSortedIndicies[i].second;
		}

		sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end());

		assert(is_sorted(beginWithIndicies.begin(), beginWithIndicies.end()));
		assert(is_sorted(endWithIndicies.begin(), endWithIndicies.end()));

		// ----------- rangesWithSortedIndicies: {valBegin, indBegin}, {valEnd, indEnd}; sorted by begin. -----------

		tree.build(0, 0, n-1);

		startTimes.resize(n);
		
		for (int i = 0; i<(int)n; i++) {
			assert(i == rangesWithSortedIndicies[i].first.second);
			startTimes[i] = tree.update(i == 0 ? 0 : startTimes[i-1], 0, n-1, rangesWithSortedIndicies[i].second.second, 1);
		}
	}


	int query(int indexBeginL, int indexBeginR, int indexEndL, int indexEndR) {
		int right = tree.query(startTimes[indexBeginR], 0, n-1, indexEndL, indexEndR);
		int left = tree.query(indexBeginL == 0 ? 0 : startTimes[indexBeginL-1], 0, n-1, indexEndL, indexEndR);
		return right-left;
	}
};

vector<int> allBeginR, allEndL;

Query queryEngine;

void makeAll() {
	allBeginR.assign(n+1, -1);
	allEndL.assign(n+1, -1);
	for (int i = 1; i<=n; i++) {
		auto pBeginR = lower_bound(queryEngine.beginWithIndicies.begin(), queryEngine.beginWithIndicies.end(), pair<int, int>{i, 1e9});
		auto pEndL = lower_bound(queryEngine.endWithIndicies.begin(), queryEngine.endWithIndicies.end(), pair<int, int>{i-1, 1e9});

		if (pBeginR != queryEngine.beginWithIndicies.begin()) allBeginR[i] = (*prev(pBeginR)).second;
		if (pEndL != queryEngine.endWithIndicies.end()) allEndL[i] = (*pEndL).second;		
	}
}


void init(signed _N, signed A[], signed B[]) {
	n = _N;

	vector<pair<int, int>> ranges(n);

	for (int i = 0; i<n; i++) {
		ranges[i].first = A[i];
		ranges[i].second = B[i];
	}

	queryEngine.initQuery(ranges);
	
	makeAll();
}






signed can(signed m, signed K[]) {
	map<int, int> projects;

	for (int i = 0; i<m; i++) {
		projects[K[i]]++;
	}

	vector<pair<int, int>> s;
	s.push_back({-1, n-1});

	for (pair<int, int> i: projects) {
		int groupsize = i.first;
		int people = i.first * i.second;


		int cnt = 0;

		int beginR = allBeginR[groupsize], endL = allEndL[groupsize];

		if (beginR == -1 || endL == -1) {return 0;}

		// esay case: this group is out of the range
		while (s.back().second < endL) {
			s.pop_back();
			if (s.empty()) return 0;
		}


		while (true) {
			int add = queryEngine.query(s.back().first+1, beginR, endL, s.back().second);

			if (cnt+add >= people) break;

			cnt += add;

			endL = s.back().second+1;

			s.pop_back();

			if (s.empty()) return 0;

		}

		int beginL = s.back().first+1;
		

		int l = endL, r = s.back().second;

		while (l<r) {
			int mid = (l+r)/2;
			int res = queryEngine.query(beginL, beginR, endL, mid);

			if (res + cnt >= people) r = mid;
			else l = mid+1;
		}

		s.push_back({beginR, l});
	}

	return 1;
}

Compilation message

teams.cpp: In member function 'void Query::seg::build(int, int, int)':
teams.cpp:22:25: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   22 |    tree[v].l = tree.size();
      |                ~~~~~~~~~^~
teams.cpp:24:25: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   24 |    tree[v].r = tree.size();
      |                ~~~~~~~~~^~
teams.cpp: In member function 'int Query::seg::update(int, int, int, int, int)':
teams.cpp:34:25: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |     int newV = tree.size();
      |                ~~~~~~~~~^~
teams.cpp:43:24: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   43 |    int newV = tree.size();
      |               ~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 29928 KB Output is correct
2 Correct 91 ms 30004 KB Output is correct
3 Correct 89 ms 29928 KB Output is correct
4 Correct 97 ms 29940 KB Output is correct
5 Correct 63 ms 30008 KB Output is correct
6 Correct 57 ms 29940 KB Output is correct
7 Correct 57 ms 30020 KB Output is correct
8 Correct 50 ms 30048 KB Output is correct
9 Correct 68 ms 29948 KB Output is correct
10 Correct 50 ms 29952 KB Output is correct
11 Correct 52 ms 29964 KB Output is correct
12 Correct 63 ms 29972 KB Output is correct
13 Correct 72 ms 29932 KB Output is correct
14 Correct 67 ms 29944 KB Output is correct
15 Correct 80 ms 30016 KB Output is correct
16 Correct 82 ms 30044 KB Output is correct
17 Correct 59 ms 30016 KB Output is correct
18 Correct 64 ms 29948 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 29952 KB Output is correct
2 Correct 105 ms 29952 KB Output is correct
3 Correct 627 ms 31812 KB Output is correct
4 Correct 87 ms 29940 KB Output is correct
5 Correct 614 ms 29924 KB Output is correct
6 Correct 534 ms 30016 KB Output is correct
7 Correct 67 ms 29944 KB Output is correct
8 Correct 418 ms 30000 KB Output is correct
9 Correct 68 ms 29976 KB Output is correct
10 Correct 51 ms 29952 KB Output is correct
11 Correct 106 ms 30040 KB Output is correct
12 Correct 767 ms 29940 KB Output is correct
13 Correct 1004 ms 30044 KB Output is correct
14 Correct 951 ms 30452 KB Output is correct
15 Correct 399 ms 30004 KB Output is correct
16 Correct 445 ms 29968 KB Output is correct
17 Correct 337 ms 29956 KB Output is correct
18 Correct 340 ms 29944 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 624 ms 222704 KB Output is correct
2 Correct 647 ms 222744 KB Output is correct
3 Correct 2779 ms 222704 KB Output is correct
4 Correct 647 ms 222744 KB Output is correct
5 Correct 2308 ms 222720 KB Output is correct
6 Correct 1891 ms 222712 KB Output is correct
7 Correct 339 ms 222700 KB Output is correct
8 Correct 1423 ms 222728 KB Output is correct
9 Correct 407 ms 222828 KB Output is correct
10 Correct 305 ms 222700 KB Output is correct
11 Correct 1008 ms 222736 KB Output is correct
12 Correct 3446 ms 222700 KB Output is correct
13 Correct 3809 ms 222704 KB Output is correct
14 Correct 3702 ms 229276 KB Output is correct
15 Correct 1353 ms 229208 KB Output is correct
16 Correct 1460 ms 229324 KB Output is correct
17 Correct 1162 ms 228732 KB Output is correct
18 Correct 1151 ms 228716 KB Output is correct