#include "teams.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second.first
#define remain second.second
using namespace std;
const int N=5e5+2,mod=1e9+7;
struct nd{
nd *l,*r;
int val;
nd(int value = 0,nd *le = NULL, nd *ri = NULL){
l = le,r = ri,val = value;
}
nd(nd *node){
l = node -> l,r = node -> r,val = node -> val;
}
};
int n;
pair<int,int> rng[N];
int lef[N];
vector<nd*>v(N+1);
void update(int idx,nd *node,int l = 1,int r = n){
if(l == r){
node -> val ++;
return;
}
int mid = (l + r)/2;
if(idx <= mid){
if(node -> l)
node -> l = new nd(node -> l);
else
node -> l = new nd();
update(idx,node -> l,l,mid);
}
else{
if(node -> r)
node -> r = new nd(node -> r);
else
node -> r = new nd();
update(idx,node -> r,mid+1,r);
}
node -> val = (node -> l ? node -> l -> val : 0) + (node -> r ? node -> r -> val : 0);
}
int get(int ql, int qr,nd *node,nd *minus = NULL,int l = 1,int r = n){
if(r < ql || qr < l) return 0;
if(ql <= l && r <= qr) return (node -> val) - (minus ? minus -> val : 0);
if(minus == NULL){
minus = new nd();
minus -> l = minus, minus -> r = minus;
}
int mid = (l + r)/2;
return (node->l ? get(ql,qr,node -> l,minus -> l,l,mid) : 0) + (node-> r ? get(ql,qr,node -> r,minus -> r,mid + 1,r) : 0);
}
void init(int en, int A[], int B[]) {
n=en;
for(int i = 1;i <= n;i++){
rng[i].F = A[i-1],rng[i].second = B[i-1];
}
sort(rng+1,rng+n+1);
v[0] = new nd();
for(int i = 1;i <= n;i++){
lef[i] = rng[i].F;
v[i] = new nd(v[i-1]);
update(rng[i].second,v[i]);
}
}
int can(int m, int K[]) {
int x[m+1];
x[0]=0;
for(int i = 1;i <= m;i++)
x[i] = K[i-1];
sort(x+1,x + m + 1);
bool ok = 1;
vector<pair<nd*,pair<int,int>>>st;
st.push_back({new nd(),{n,0}});
for(int i = 1;i <= m;i++){
int u = upper_bound(lef+1,lef+n+1,x[i])-lef-1;
//cout<<"u "<<u<<endl;
nd *root = v[u];
int ans = x[i];
int b = x[i],e = -1;
while(st.size()){
//cout<<b<<" "<<st.back().S;
//cout<<"get+remain: "<<gr<<endl;
while(b > st.back().S){
st.pop_back();
//cout<<b<<" "<<st.back().S;
}
int gr = get(b,st.back().S,root,st.back().F) + st.back().remain;
if(ans <= gr)
break;
ans -= gr;
b = st.back().S+1;
st.pop_back();
}
if(st.size())
e = st.back().S;
else
return 0;
nd *minus = st.back().F;
int last = e,remaining=0;
while(b <= e){
int mid = (b + e)/2;
ll cur = get(b,mid,root,minus);
if(mid == st.back().S)
cur+=st.back().remain;
if(cur >= ans){
last = mid,e = mid - 1;
remaining = cur - ans;
}
else
b=mid+1;
}
//cout<<"last: "<<last<<" remaining: "<<remaining<<"\n";
assert(!st.size() || st.back().S >= last);
if (st.size() && st.back().S == last)
st.pop_back();
st.push_back({root,{last,remaining}});
}
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... |