# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
828508 |
2023-08-17T10:37:37 Z |
Josia |
팀들 (IOI15_teams) |
C++17 |
|
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();
| ~~~~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |