#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
//#include "tournament.h"
int tree[110001];
int aa[100001];
int bb[100001];
int n;
void u(int i,int j){
while(i<110001){
tree[i]+=j;
i+=(i&-i);
}
}
int s(int i){
int su=0;
while(i>0){
su+=tree[i];
i-=(i&-i);
}
return su;
}
int find(int x){
int ind=0;
int su=0;
for(int i=19;i>=0;i--){
if((1<<i)+ind<=n){
if(su+tree[ind+(1<<i)]<=x){
ind+=(1<<i);
su+=tree[ind];
}
}
}
return ind;
}
int find2(int x){
int ind=0;
int su=0;
for(int i=19;i>=0;i--){
if((1<<i)+ind<=n){
if(su+tree[ind+(1<<i)]<x){
ind+=(1<<i);
su+=tree[ind];
}
}
}
return ind+1;
}
int tree2[110001];
void u2(int i,int j){
while(i<110001){
tree2[i]+=j;
i+=(i&-i);
}
}
int s2(int i){
int su=0;
while(i>0){
su+=tree2[i];
i-=(i&-i);
}
return su;
}
int tree3[400001];
int kk[100001];
void build(int no,int l,int r){
if(l==r){
tree3[no]=kk[l];
}
else{
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
}
}
int query(int no,int l,int r,int aa,int bb){
if(r<aa or bb<l){
return 0;
}
// cout<<l<<':'<<r<<endl;
if(aa<=l and r<=bb){
return tree3[no];
}
int mid=(l+r)/2;
return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int GetBestPosition(int nn, int c, int r, int k[], int ss[], int tt[]) {
n=nn;
if(n==1){
while(true){
continue;
}
}
for(int i=0;i<n;i++){
u(i+1,1);
}
for(int i=0;i<n-1;i++){
kk[i]=k[i];
}
build(0,0,n-2);
for(int j=0;j<c;j++){
aa[j]=find2(ss[j]+1);
bb[j]=find(tt[j]+1);
for(int i=ss[j]+1;i<=tt[j];i++){
u(i+1,-1);
}
cout<<aa[j]<<","<<bb[j]<<endl;
aa[j]-=1;
bb[j]-=2;
// cout<<aa[j]<<","<<bb[j]<<endl;
// cout<<endl;
if(query(0,0,n-2,aa[j],bb[j])<r){
// cout<<j<<endl;
u2(aa[j]+1,1);
u2(bb[j]+3,-1);
cout<<aa[j]+1<<"::"<<bb[j]+2<<endl;
}
}
int mi=-1;
int ind=0;
for(int i=0;i<n;i++){
int x=s2(i+1);
cout<<i<<"::"<<x<<","<<ind<<endl;
if(x>mi){
mi=x;
ind=i;
}
}
return ind;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
3616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
