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 <bits/stdc++.h>
using namespace std;
#define PB push_back
struct BIT{
int n,bit[100005];
void ini(int x){
n=x;
for(int i=0;i<=n;i++)bit[i]=0;
}
void add(int a,int x){
a++;
while(a<=n){
bit[a]+=x;
a+=(a&-a);
}
}
int sum(int a){
int res=0;
a++;
while(a>0){
res+=bit[a];
a-=(a&-a);
}
return res;
}
int serch(int x){
int l=-1,r=n-1;
while(r-l>1){
int m=(l+r)/2;
if(sum(m)>=x)r=m;
else l=m;
}
return r;
}
};
int n,m,ans,rst[100005],in;
vector<int>f[100005],t[100005];
bool lo[100005],ro[100005];
BIT bit1,bit2;
int GetBestPosition(int N, int C, int p, int *c, int *a, int *b) {
n=N,m=C;
bit1.ini(n);
bit2.ini(n);
for(int i=1;i<n;i++)bit1.add(i,1),bit2.add(i,1);
for(int i=0;i<m;i++){
a[i]=bit1.serch(a[i]);
b[i]=bit2.serch(b[i]);
for(int j=a[i]+1;j<=b[i];j++)bit1.add(j,-1);
for(int j=a[i];j<b[i];j++)bit2.add(j,-1);
f[a[i]].PB(i);
t[b[i]].PB(i);
}
int l=-1,r=0;
for(int i=0;i<n;i++){
for(int j=0;j<f[i].size();j++){
int x=f[i][j];
if(ro[x])in++;
lo[x]=true;
}
while(r<n&&(r<=i||c[r-1]<=p)){
for(int j=0;j<t[r].size();j++){
int x=t[r][j];
if(lo[x])in++;
ro[x]=true;
}
r++;
}
rst[i]=in;
if(in>rst[ans])ans=i;
for(int j=0;j<t[i].size();j++){
int x=t[i][j];
if(lo[x])in--;
ro[x]=false;
}
if(i<n-1&&c[i]>p){
while(l<i){
l++;
for(int j=0;j<f[l].size();j++){
int x=f[l][j];
if(ro[x])in--;
lo[x]=false;
}
}
}
}
return ans;
}
Compilation message (stderr)
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<f[i].size();j++){
~^~~~~~~~~~~~
tournament.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t[r].size();j++){
~^~~~~~~~~~~~
tournament.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t[i].size();j++){
~^~~~~~~~~~~~
tournament.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<f[l].size();j++){
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |