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 <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define DIMN 200010
#define INF 1000000000
using namespace std;
int n;
int v[DIMN],aint[4*DIMN],v2[DIMN],prefix[DIMN],sufix[DIMN],w[DIMN];
int findd (int nr,int ok){ /// primul > sau ult <=
int st,dr,mid;
st = 1;
dr = n;
while (st<=dr){
mid = (st + dr)/2;
if (v2[mid]<=nr)
st = mid + 1;
else dr = mid - 1;
}
if (ok == 0)
return dr;
return st;
}
void update (int nod,int st,int dr,int p,int val){
int mid = (st + dr)/2;
if (st == dr){
aint[nod] = max(aint[nod] , val);
return;
}
if (p<=mid)
update(2*nod,st,mid,p,val);
else update(2*nod+1,mid+1,dr,p,val);
aint[nod] = max (aint[2*nod] , aint[2*nod+1]);
}
int query (int nod,int st,int dr,int l, int r){
int mid = (st + dr)/2;
int sol = -INF;
if (l > r)
return -INF;
if (l<=st && dr<=r){
return aint[nod];
}
if (l<=mid)
sol = query(2*nod,st,mid,l,r);
if (mid+1<=r)
sol = max(sol , query(2*nod+1,mid+1,dr,l,r));
return sol;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int x,i,dist,elem,sol,st,dr,mid;
fscanf (fin,"%d%d",&n,&x);
for (i=1;i<=n;i++){
fscanf (fin,"%d",&v[i]);
v2[i] = v[i];
}
sort (v2 + 1, v2 + n + 1);
dist = 0;
for (i=1;i<=n;i++){
if (i==1 || v2[i]!=v2[i-1])
v2[++dist] = v2[i];
}
v2[0] = -2000000000;
v2[n+1] = 2000000000;
elem = 0;
for (i=1;i<=n;i++){
st = 1;
dr = elem;
while (st<=dr){
mid = (st + dr)/2;
if (v[w[mid]] < v[i])
st = mid + 1;
else dr = mid - 1;
}
if (st == elem + 1){
w[++elem] = i;
prefix[i] = elem;
}
else {
if (v[i] < v[w[st]])
w[st] = i;
prefix[i] = st;
}
}
/// reverse v
st = 1;
dr = n;
while (st<dr){
swap(v[st] , v[dr]);
st++;
dr--;
}
/// gata reverse , calcul sufix
elem = 0;
for (i=1;i<=n;i++){
st = 1;
dr = elem;
while (st<=dr){
mid = (st + dr)/2;
if (v[w[mid]] > v[i])
st = mid + 1;
else dr = mid - 1;
}
if (st == elem + 1){
w[++elem] = i;
sufix[n-i+1] = elem;
}
else {
if (v[i] > v[w[st]])
w[st] = i;
sufix[n-i+1] = st;
}
}
/// reverse v
st = 1;
dr = n;
while (st<dr){
swap(v[st] , v[dr]);
st++;
dr--;
}
/// gata reverse
/// caz 1 : aduni x la un sufix
sol = prefix[n];
for (i=1;i<=n;i++){
/// ce obtinem daca adaugam de la i la n o valoare
/// vreau sa gasesc care e prefix[j] maxim , j<i a.i v[j] < v[i] + x
if (i!=1)
sol = max (sol , sufix[i] + query(1,1,n,1,findd(v[i]+x-1,0))); /// ult <=
update (1,1,n,findd(v[i],0) , prefix[i]);
}
/// caz 2 : scazi x de la un prefix
memset (aint,0,sizeof(aint));
for (i=n;i;i--){
/// ce obtinem daca adunam -x de la 1 la i
/// vreau sa gasesc care e sufix[j] maxim , j > i, v[i] - x < v[j]
if (i!=n){
sol = max (sol , prefix[i] + query(1,1,n,findd(v[i]-x,1),n)); /// prm >
}
update (1,1,n,findd(v[i],0) , sufix[i]);
}
fprintf (fout,"%d",sol);
return 0;
}
Compilation message (stderr)
glo.cpp: In function 'int main()':
glo.cpp:54:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&x);
~~~~~~~^~~~~~~~~~~~~~~~~~
glo.cpp:56:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&v[i]);
~~~~~~~^~~~~~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |