이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int val, lpt, rpt;
};
const int maxn = 5e5 + 5, maxN = 2e6 + 5;
int n;
vector<node> seg[maxN];
int pos[maxn];
void build(int id, int l, int r) {
seg[id] = {{0, 0, 0}};
if (l==r) return;
int mid = (l+r)/2;
build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int target) {
if (r<target || target<l) return;
if (l==r) {
int val = seg[id].back().val + 1;
seg[id].push_back({val, 0, 0});
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, target); update(id*2+1, mid+1, r, target);
seg[id].push_back({seg[id*2].back().val + seg[id*2+1].back().val, (int)seg[id*2].size()-1, (int)seg[id*2+1].size()-1});
}
int qry(int id, int pt, int l, int r, int findl, int findr) {
if (r<findl || findr<l) return 0;
if (findl<=l && r<=findr) return seg[id][pt].val;
int mid = (l+r)/2;
return qry(id*2, seg[id][pt].lpt, l, mid, findl, findr) + qry(id*2+1, seg[id][pt].rpt, mid+1, r, findl, findr);
}
void init(int N, int A[], int B[]) {
n = N;
build(1, 1, n);
vector<int> vec[n+1];
for (int i=0;i<n;i++) vec[A[i]].push_back(B[i]);
pos[0] = 0;
for (int i=1;i<=n;i++) {
for (int j:vec[i]) update(1, 1, n, j);
pos[i] = (int)seg[1].size() - 1;
}
}
int can(int m, int a[]) {
sort(a, a+m);
int left = 0, last = 0;
for (int i=0;i<m;i++) {
left = min(qry(1, pos[last], 1, n, a[i], n), left);
left += qry(1, pos[a[i]], 1, n, a[i], n) - qry(1, pos[last], 1, n, a[i], n);
left -= a[i];
if (left<0) return 0;
last = a[i];
}
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... |