#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
//#define int long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e5;
set<int> st;
set<int> itr it;
vector<pii> query;
vector<int> vec[MAX];
int N,R,res,rep[MAX],lol[MAX],dp[MAX],arr[MAX],deg[MAX],start[MAX],finish[MAX];
struct SegTree
{
vector<pii> seg;
SegTree()
{
}
void init(int N)
{
seg.resize(4*N);
return ;
}
void build(int low,int high,int node)
{
if(low==high)
{
seg[node]=mp(arr[low],1);
return ;
}
int mid=(low+high)/2;
build(low,mid,2*node);
build(mid+1,high,2*node+1);
seg[node].first=max(seg[2*node].first,seg[2*node+1].first);
seg[node].second=seg[2*node].second+seg[2*node+1].second;
return ;
}
void update(int low,int high,int node,int idx)
{
if(low==high)
{
seg[node].second=0;
return ;
}
int mid=(low+high)/2;
if(idx>=low and idx<=mid)
update(low,mid,2*node,idx);
else
update(mid+1,high,2*node+1,idx);
seg[node].second=seg[2*node].second+seg[2*node+1].second;
return ;
}
int get(int low,int high,int node,int idx)
{
if(low==high)
return low;
int mid=(low+high)/2;
if(seg[2*node].second>=idx)
return get(low,mid,2*node,idx);
else
return get(mid+1,high,2*node+1,idx-seg[2*node].second);
}
int query(int low,int high,int node,int qlow,int qhigh)
{
if(low>high or qlow>qhigh or qhigh<low or qlow>high)
return 0;
if(low>=qlow and high<=qhigh)
return seg[node].first;
int mid=(low+high)/2;
return max(query(low,mid,2*node,qlow,qhigh),query(mid+1,high,2*node+1,qlow,qhigh));
}
} S;
void ConstructTree()
{
int l,r,cur=N+1;
for(int A=1;A<=N+1;A++)
{
rep[A]=A;
st.insert(A);
}
for(auto A:query)
{
l=S.get(1,N,1,A.first);
r=S.get(1,N,1,A.second);
//cout<<l<<" "<<r<<"\n";
for(it=st.lower_bound(l);it!=st.end();it++)
{
if(*it>r)
break;
vec[cur].pb(rep[*it]);
deg[rep[*it]]++;
if(*it!=l)
S.update(1,N,1,*it);
}
rep[l]=cur++;
//cout<<*st.lower_bound(l)<<" "<<*st.lower_bound(r)<<"ha ha \n";
st.erase(st.upper_bound(l),st.upper_bound(r));
}
return ;
}
void dfs(int node,int hei)
{
dp[node]=0;
start[node]=node<=N?node:4*N;
finish[node]=node<=N?node:0;
for(auto A:vec[node])
{
dfs(A,hei+1);
start[node]=min(start[node],start[A]);
finish[node]=max(finish[node],finish[A]);
dp[node]=max(dp[node],dp[A]+1);
}
if(S.query(1,N,1,start[node],finish[node]-1)<R)
res=max(res,dp[node]);
return ;
}
int GetBestPosition(int n, int C, int r, int *K, int *S_, int *E)
{
res=0;
N=n,R=r;
for(int A=0;A<N;A++)
arr[A+1]=K[A];
S.init(N);
S.build(1,N,1);
for(int A=0;A<C;A++)
query.pb(mp(S_[A]+1,E[A]+1));
ConstructTree();
for(int A=1;A<=N+C;A++)
if(!deg[A])
dfs(A,0);
return res;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
int K[]={1,0,2,4},seg[]={1,0,0},E[]={3,1,1};
cout<<GetBestPosition(5,3,3,K,seg,E);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
2752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
10008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
