Submission #108926

#	Time	Username	Problem	Language	Result	Execution time	Memory
108926		AdrienVannson	Two Antennas (JOI19_antennas)	C++17	35 / 100	3032 ms	17772 KiB

antennas

#pragma GCC optimize "Ofast,unroll-loops,omit-frame-pointer,inline"

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;
using ll = long long;

const int oo = 1000*1000*1000;

const int NB_MAX_ANTENNES = 200*1000 + 42;

struct Antenne
{
    int pos;
    int hauteur;
    int distMin, distMax;
};

int nbAntennes;
Antenne antennes[NB_MAX_ANTENNES];


/*
 * Arbre binaire
 */

const int NB_FEUILLES = 1<<18;
const int NB_NOEUDS = 2*NB_FEUILLES;

pair<int, int> valeurs[NB_NOEUDS]; // {min, max}

void setValeur (const int pos, const int nouvelleValeur)
{
    int iNoeud = NB_FEUILLES + pos;

    if (nouvelleValeur == -1) {
        valeurs[iNoeud] = make_pair(+oo, -oo);
    }
    else {
        valeurs[iNoeud] = make_pair(nouvelleValeur, nouvelleValeur);
    }

    for (iNoeud/=2; iNoeud>=1; iNoeud/=2) {
        valeurs[iNoeud].first = min(valeurs[iNoeud*2].first, valeurs[iNoeud*2+1].first);
        valeurs[iNoeud].second = max(valeurs[iNoeud*2].second, valeurs[iNoeud*2+1].second);
    }
}

pair<int, int> getMinmax (const int debut, const int fin,
                          const int iNoeud=1, const int debutActuel=0, const int finActuelle=NB_FEUILLES)
{
    if (debutActuel >= debut && finActuelle <= fin) {
        return valeurs[iNoeud];
    }
    if (debutActuel >= fin || finActuelle <= debut) {
        return make_pair(+oo, -oo);
    }

    const int milieuActuel = (debutActuel + finActuelle) / 2;

    const pair<int, int> res1 = getMinmax(debut, fin, iNoeud*2, debutActuel, milieuActuel);
    const pair<int, int> res2 = getMinmax(debut, fin, iNoeud*2+1, milieuActuel, finActuelle);

    return make_pair( min(res1.first, res2.first), max(res1.second, res2.second) );
}


/*
 * Main
 */

vector<pair<int, int>> evenements[NB_MAX_ANTENNES]; // {pos, 2*iAntenne+estDebut}

int calcRequete (const int debutRequete, const int finRequete)
{
    int res = -1;

    for (int iAntenne=0; iAntenne<nbAntennes; iAntenne++) {
        const Antenne &antenne = antennes[iAntenne];

        // Traiter les événements
        for (const pair<int, int> &evenement : evenements[iAntenne]) {
            const Antenne &ant = antennes[evenement.second / 2];

            if (evenement.second % 2 == 1) { // Début
                setValeur(ant.pos, ant.hauteur);
            }
            else {
                setValeur(ant.pos, -1);
            }
        }

        if (debutRequete <= iAntenne && iAntenne < finRequete) {
            // Trouver le max pour l'antenne actuelle
            const int debut = max(antenne.pos + antenne.distMin, debutRequete);
            const int fin = min(antenne.pos + antenne.distMax + 1, finRequete);

            if (debut >= nbAntennes) {
                continue;
            }

            const pair<int, int> minmax = getMinmax(debut, fin);

            const int score1 = minmax.second - antenne.hauteur;
            const int score2 = antenne.hauteur - minmax.first;

            res = max( max(score1, score2), res );
        }
    }

    return res;
}

int main ()
{
    scanf("%d", &nbAntennes);

    for (int i=0; i<nbAntennes; i++) {
        antennes[i].pos = i;
        scanf("%d %d %d", &antennes[i].hauteur, &antennes[i].distMin, &antennes[i].distMax);

        setValeur(i, -1);
    }

    int nbRequetes;
    scanf("%d", &nbRequetes);

    if (nbAntennes <= 2000) {
        struct Point
        {
            int debut, fin;
            bool estRequete;
            int info; // iRequete ou score

            bool operator< (const Point &autre)
            {
                if (fin != autre.fin) {
                    return fin < autre.fin;
                }
                if (debut != autre.debut) {
                    return debut > autre.debut;
                }
                return !estRequete;
            }
        };

        vector<Point> points;
        int resRequetes[200*1000];

        for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
            int debutRequete, finRequete;
            scanf("%d %d", &debutRequete, &finRequete);
            debutRequete--, finRequete--; // FIN INCLUSE

            points.push_back(Point{debutRequete, finRequete, true, iRequete});
        }

        for (int a=0; a<nbAntennes; a++) {
            for (int b=a+1; b<nbAntennes; b++) {
                if (a < b-antennes[b].distMax || a > b-antennes[b].distMin) {
                    continue;
                }
                if (b > a+antennes[a].distMax || b < a+antennes[a].distMin) {
                    continue;
                }

                points.push_back(Point{a, b, false, abs(antennes[a].hauteur - antennes[b].hauteur)});
            }
        }

        sort(points.begin(), points.end());

        for (const Point &point : points) {

            if (point.estRequete) {
                resRequetes[point.info] = getMinmax(point.debut, nbAntennes).second;

                if (resRequetes[point.info] == -oo) {
                    resRequetes[point.info] = -1;
                }
            }
            else {
                if (point.info > valeurs[NB_FEUILLES+point.debut].second) {
                    setValeur(point.debut, point.info);
                }
            }

        }

        for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
            printf("%d\n", resRequetes[iRequete]);
        }
    }
    else {
        for (int i=0; i<nbAntennes; i++) {
            const Antenne &ant = antennes[i];
            evenements[ max(ant.pos - ant.distMax, 0) ].push_back(make_pair(ant.pos, 2*i+1));
            evenements[ max(ant.pos - ant.distMin + 1, 0) ].push_back(make_pair(ant.pos, 2*i));
        }

        for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
            int debutRequete, finRequete;
            scanf("%d %d", &debutRequete, &finRequete);
            debutRequete--;

            printf("%d\n", calcRequete(debutRequete, finRequete));
        }
    }
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbAntennes);
     ~~~~~^~~~~~~~~~~~~~~~~~~
antennas.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &antennes[i].hauteur, &antennes[i].distMin, &antennes[i].distMax);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbRequetes);
     ~~~~~^~~~~~~~~~~~~~~~~~~
antennas.cpp:155:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &debutRequete, &finRequete);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &debutRequete, &finRequete);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65