This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++;
if(l+1==r){
return momold;
}
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;
seg.build(0, n+1, 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+1, last, b[i]);
last = seg.root[a[i]];
}
last=0;
for(int i=1; i<=n; i++){
if(seg.root[i]==0){
seg.root[i] = last;
}
else{
last = seg.root[i];
}
}
n++;
}
int can(int m, int K[]) {
vector<int> k(m);
for(int i=0; i<m; i++){
k[i]=K[i];
}
sort(k.begin(), k.end());
k.push_back(n);
bool pos=true;
int add=0;
for(int i=0; i<m; i++){
//cout << i << " " << k[i] << " " << add << "\n";
int r=seg.root[k[i]];
if(seg.tree[r].val < k[i]+add){
pos=false;
}
int sumuntilnext=seg.query(0, n, r, 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... |