Submission #156001

#	Time	Username	Problem	Language	Result	Execution time	Memory
156001		Ruxandra985	Global Warming (CEOI18_glo)	C++14	100 / 100	404 ms	8972 KiB

glo

#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]);
         ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25