Submission #156001

#TimeUsernameProblemLanguageResultExecution timeMemory
156001Ruxandra985Global Warming (CEOI18_glo)C++14
100 / 100
404 ms8972 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...