이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
int left=-1;
int right=-1;
int val=0;
};
struct segtree{
vector<node> tree;
map<int, int> root;
int mom=0;
int build(int l, int r, int v){
tree.push_back({-1, -1, 0});
mom++;
if(l+1==r){
return v;
}
int m=l+(r-l)/2;
tree[v].left = build(l, m, mom);
tree[v].right = build(m, r, mom);
return v;
}
int update(int l, int r, int v, int x){ //returns node index
if(x<l || r<=x) return v;
int momold=mom;
tree.push_back(tree[v]);
tree[mom].val++;
mom++;
int m=l+(r-l)/2;
tree[momold].left = update(l, m, tree[v].left, x);
tree[momold].right = update(m, r, tree[v].right, x);
return momold;
}
int query(int l, int r, int v, int ql, int qr){ //returns sum
if(qr<=l || r<=ql) return 0;
if(ql<=l && r<=qr){
return tree[v].val;
}
int m=l+(r-l)/2;
return query(l, m, tree[v].left, ql, qr) + query(m, r, tree[v].right, ql, qr);
}
};
segtree seg;
int n=0;
void init(int N, int a[], int b[]) {
N++;
n=N;
seg.build(0, n, 0);
seg.root[-1]=0;
vector<int> sorted(n, 0);
iota(sorted.begin(), sorted.end(), 0);
sort(sorted.begin(), sorted.end(), [&](int i, int j){
return a[i]<a[j];
});
int last=0;
for(auto i: sorted){
seg.root[a[i]] = seg.update(0, n, last, b[i]);
last = seg.root[a[i]];
}
}
int can(int m, int K[]) {
vector<int> k(m);
for(int i=0; i<m; i++){
k[i]=K[i];
}
k.push_back(n);
bool pos=true;
int add=0;
for(int i=0; i<m; i++){
int r=seg.root[k[i]];
if(seg.tree[r].val < k[i]+add){
pos=false;
}
int sumuntilnext=seg.query(0, n, 0, k[i], k[i+1]);
add = max(0, k[i]+add - sumuntilnext);
}
if(0<add) pos=false;
return pos;
}
# | 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... |