oj.uz

Submission #726165

# Submission time Handle Problem Language Result Execution time Memory
726165 2023-04-18T15:47:23 Z reitracn Measures (CEOI22_measures) C++17
35 / 100
 220 ms 17480 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 15320 KB Output is correct
2 Correct 178 ms 17224 KB Output is correct
3 Correct 143 ms 17212 KB Output is correct
4 Correct 166 ms 15024 KB Output is correct
5 Correct 143 ms 16304 KB Output is correct
6 Correct 143 ms 15428 KB Output is correct
7 Correct 148 ms 16316 KB Output is correct
8 Correct 143 ms 15148 KB Output is correct
9 Correct 156 ms 15024 KB Output is correct
10 Correct 155 ms 17480 KB Output is correct
11 Correct 142 ms 15824 KB Output is correct
12 Correct 143 ms 16828 KB Output is correct
13 Correct 152 ms 15028 KB Output is correct
14 Correct 141 ms 16948 KB Output is correct
15 Correct 155 ms 16812 KB Output is correct
16 Correct 162 ms 14648 KB Output is correct
17 Correct 151 ms 16328 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 15320 KB Output is correct
2 Correct 178 ms 17224 KB Output is correct
3 Correct 143 ms 17212 KB Output is correct
4 Correct 166 ms 15024 KB Output is correct
5 Correct 143 ms 16304 KB Output is correct
6 Correct 143 ms 15428 KB Output is correct
7 Correct 148 ms 16316 KB Output is correct
8 Correct 143 ms 15148 KB Output is correct
9 Correct 156 ms 15024 KB Output is correct
10 Correct 155 ms 17480 KB Output is correct
11 Correct 142 ms 15824 KB Output is correct
12 Correct 143 ms 16828 KB Output is correct
13 Correct 152 ms 15028 KB Output is correct
14 Correct 141 ms 16948 KB Output is correct
15 Correct 155 ms 16812 KB Output is correct
16 Correct 162 ms 14648 KB Output is correct
17 Correct 151 ms 16328 KB Output is correct
18 Incorrect 220 ms 16216 KB Output isn't correct
19 Halted 0 ms 0 KB -