Submission #726165

#	Time	Username	Problem	Language	Result	Execution time	Memory
726165		reitracn	Measures (CEOI22_measures)	C++17	35 / 100	220 ms	17480 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int INF = LLONG_MAX/6;

enum OPERATOR{MIN = 0, MAX};

int TYPE;


int compare(int u, int v)
{
    if(TYPE == MIN)
        return min(u, v);
    else if(TYPE == MAX)
        return max(u, v);
    else
    {
        printf("ERROR NOT AN OPERATOR !!");
        return -1;
    }

}

struct Point
{
    int pos;
    int idx;
    int altitude;
    Point(int p_, int i_, int a_)
    {
        pos = p_;
        idx = i_;
        altitude = a_;
    }
    Point(){}

    bool operator<(const Point& autre) const
    {
        if(TYPE == MAX)
        {
            if(pos == autre.pos)
            {

                return altitude > autre.altitude; // / // / // /////
            }
            return pos < autre.pos;
        }
        else if(TYPE == MIN)
        {
            if(pos == autre.pos)
            {
                return altitude < autre.altitude; // / // / // /////
            }
            return pos > autre.pos;
        }
        else
        {
            printf("ERROR");
            return pos < autre.pos;
        }

    }
};


vector<Point> points;
vector<int > ansQueries;
vector<int> ab;
int NN = 1;


void upd(int nde)
{
    ab[nde] = compare(ab[nde*2], ab[nde*2 +1]);
    if(nde > 1)
        upd(nde/ 2);
}

int query(int nde, int RB, int RE, int GB, int GE)
{
    if(GB > RE || RB > GE)
    {
        if(TYPE == MAX)
            return -INF;
        else
            return INF;
    }
    if(RB >= GB && RE <= GE)
    {
        return ab[nde];
    } 
    int MID = (RB + RE)/2;
    return compare(query(nde * 2, RB, MID, GB, GE), query(nde *2 +1, MID+1, RE, GB, GE));
}



signed main()
{
    int nbInit, nbQueriesDemandees, D;
    scanf("%lld%lld%lld", &nbInit, &nbQueriesDemandees, &D);
    int nbQueriesTot = nbInit + nbQueriesDemandees;
    while (NN < nbQueriesTot + 1) NN*= 2;///

    vector<int > queries(nbInit+ nbQueriesDemandees);

    ansQueries.assign(nbQueriesTot, 0);

    for(int iN = 0; iN < nbInit; iN++)
    {
        scanf("%lld", &queries[iN]);
    }
    for(int iQ = nbInit; iQ < nbQueriesTot; iQ++)
    {

        scanf("%lld", &queries[iQ]);
    }  
    
    for(int iQ = 0; iQ< nbQueriesTot; iQ++)
    {
        int pos = queries[iQ];
        int idx = iQ;
        int cout = pos - (idx+1)*D;////
        //printf("[%lld:%lld], ", pos, cout);
        points.push_back(Point(pos, idx, cout));
    }
    //printf("\n");

    //GAUCHE -> DROITE
    TYPE = MAX;
    sort(points.begin(), points.end());
    ab.clear();
    ab.assign(2*NN, -INF);
    
    for(int pointAct = 0; pointAct < nbQueriesTot; pointAct++)
    {
        Point pt = points[pointAct];
        int idxAct = pt.idx;
        int maxLeft = query(1, 0, NN-1, 0, idxAct);
        int minRight = pt.altitude;
        ansQueries[idxAct] = max(ansQueries[idxAct], maxLeft - minRight);
        //printf("%lld/%lld/%lld->   minRight:%lld | maxLeft:%lld --> %lld\n", pt.pos, idxAct, pt.altitude,minRight, maxLeft, ansQueries[idxAct]);

        ab[idxAct + NN] = pt.altitude;
        upd((idxAct + NN)/2);
         
    }

    
    
    //printf("-------\n");
    
    
    //DROITE -> GAUCHE
    TYPE = MIN;
    sort(points.begin(), points.end());
    ab.clear();
    ab.assign(2*NN, INF);
    for(int pointAct = 0; pointAct < nbQueriesTot; pointAct++)
    {
        Point pt = points[pointAct];
        int idxAct = pt.idx;
        int minRight = query(1, 0, NN-1, 0, idxAct);//
        int maxLeft = pt.altitude;
        ansQueries[idxAct] = max(ansQueries[idxAct], maxLeft - minRight);
        //printf("%lld/%lld/%lld->   minRight:%lld | maxLeft:%lld --> %lld\n", pt.pos, idxAct, pt.altitude,minRight, maxLeft, ansQueries[idxAct]);
        ab[idxAct + NN] = pt.altitude;
        upd((idxAct + NN)/2);   
    } 

    for(int iQ =1; iQ < nbQueriesTot; iQ++)
    {
        ansQueries[iQ] = max(ansQueries[iQ], ansQueries[iQ-1]);
    }
    for(int iQ = nbQueriesTot - nbQueriesDemandees; iQ < nbQueriesTot; iQ++)
    {
        printf("%lld", ansQueries[iQ]/2);
        if(ansQueries[iQ] % 2 == 1)
        {
            printf(".5");
        }
        printf(" ");
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%lld%lld%lld", &nbInit, &nbQueriesDemandees, &D);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf("%lld", &queries[iN]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf("%lld", &queries[iQ]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 0 / 41