이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) {
// cerr << v << "\n";
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;
unordered_map<int, 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[-1] = 0;
for (int i = 0; i<(int)n; i++) {
assert(i == rangesWithSortedIndicies[i].first.second);
startTimes[i] = tree.update(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(startTimes[indexBeginL-1], 0, n-1, indexEndL, indexEndR);
return right-left;
}
};
Query queryEngine;
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);
}
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) {
// for (auto j: s) cerr << j.first << " " << j.second << "; ";
// cerr << "\n";
int groupsize = i.first;
int people = i.first * i.second;
// esay case: this group is out of the range
while (s.back().second < groupsize) {
s.pop_back();
if (s.empty()) return 0;
}
int cnt = 0;
int beginR, endL;
auto pBeginR = prev(lower_bound(queryEngine.beginWithIndicies.begin(), queryEngine.beginWithIndicies.end(), pair<int, int>{groupsize, 1e9}));
auto pEndL = lower_bound(queryEngine.endWithIndicies.begin(), queryEngine.endWithIndicies.end(), pair<int, int>{groupsize-1, 1e9});
if (pBeginR == prev(queryEngine.beginWithIndicies.begin()) || pEndL == queryEngine.beginWithIndicies.end()) return 0;
beginR = (*pBeginR).second;
endL = (*pEndL).second;
while (true) {
int add = queryEngine.query(s.back().first+1, beginR, endL, s.back().second);
if (cnt+add >= people) break;
endL = s.back().second+1;
s.pop_back();
if (s.empty()) return 0;
}
// cerr << cnt << "\n";
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;
}
// cerr << queryEngine.query(beginL, beginR, endL, l) << "\n";
s.push_back({beginR, l});
}
return 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |