#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5248 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
5248 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5248 KB |
Output is correct |
9 |
Correct |
7 ms |
5248 KB |
Output is correct |
10 |
Correct |
9 ms |
5248 KB |
Output is correct |
11 |
Correct |
8 ms |
5120 KB |
Output is correct |
12 |
Correct |
8 ms |
5248 KB |
Output is correct |
13 |
Correct |
7 ms |
5248 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
8 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5240 KB |
Output is correct |
23 |
Correct |
7 ms |
5120 KB |
Output is correct |
24 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5248 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
5248 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5248 KB |
Output is correct |
9 |
Correct |
7 ms |
5248 KB |
Output is correct |
10 |
Correct |
9 ms |
5248 KB |
Output is correct |
11 |
Correct |
8 ms |
5120 KB |
Output is correct |
12 |
Correct |
8 ms |
5248 KB |
Output is correct |
13 |
Correct |
7 ms |
5248 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
8 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5240 KB |
Output is correct |
23 |
Correct |
7 ms |
5120 KB |
Output is correct |
24 |
Correct |
7 ms |
5120 KB |
Output is correct |
25 |
Correct |
104 ms |
10852 KB |
Output is correct |
26 |
Correct |
42 ms |
9536 KB |
Output is correct |
27 |
Correct |
161 ms |
14732 KB |
Output is correct |
28 |
Correct |
162 ms |
14560 KB |
Output is correct |
29 |
Correct |
106 ms |
10976 KB |
Output is correct |
30 |
Correct |
114 ms |
12132 KB |
Output is correct |
31 |
Correct |
147 ms |
11740 KB |
Output is correct |
32 |
Correct |
229 ms |
14556 KB |
Output is correct |
33 |
Correct |
188 ms |
12508 KB |
Output is correct |
34 |
Correct |
121 ms |
10836 KB |
Output is correct |
35 |
Correct |
181 ms |
13020 KB |
Output is correct |
36 |
Correct |
163 ms |
14608 KB |
Output is correct |
37 |
Correct |
84 ms |
9192 KB |
Output is correct |
38 |
Correct |
133 ms |
11100 KB |
Output is correct |
39 |
Correct |
31 ms |
6224 KB |
Output is correct |
40 |
Correct |
134 ms |
11216 KB |
Output is correct |
41 |
Correct |
124 ms |
10472 KB |
Output is correct |
42 |
Correct |
194 ms |
11184 KB |
Output is correct |
43 |
Correct |
80 ms |
7924 KB |
Output is correct |
44 |
Correct |
163 ms |
11184 KB |
Output is correct |
45 |
Correct |
33 ms |
6768 KB |
Output is correct |
46 |
Correct |
140 ms |
11244 KB |
Output is correct |
47 |
Correct |
40 ms |
7016 KB |
Output is correct |
48 |
Correct |
132 ms |
11172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
16436 KB |
Output is correct |
2 |
Correct |
231 ms |
17616 KB |
Output is correct |
3 |
Correct |
150 ms |
14400 KB |
Output is correct |
4 |
Correct |
215 ms |
17660 KB |
Output is correct |
5 |
Correct |
97 ms |
11500 KB |
Output is correct |
6 |
Correct |
217 ms |
17636 KB |
Output is correct |
7 |
Correct |
200 ms |
16316 KB |
Output is correct |
8 |
Correct |
222 ms |
17636 KB |
Output is correct |
9 |
Correct |
36 ms |
7536 KB |
Output is correct |
10 |
Correct |
241 ms |
17592 KB |
Output is correct |
11 |
Correct |
134 ms |
13292 KB |
Output is correct |
12 |
Correct |
251 ms |
17772 KB |
Output is correct |
13 |
Correct |
130 ms |
17128 KB |
Output is correct |
14 |
Correct |
134 ms |
16912 KB |
Output is correct |
15 |
Correct |
123 ms |
16616 KB |
Output is correct |
16 |
Correct |
125 ms |
16360 KB |
Output is correct |
17 |
Correct |
142 ms |
17292 KB |
Output is correct |
18 |
Correct |
145 ms |
16360 KB |
Output is correct |
19 |
Correct |
145 ms |
16616 KB |
Output is correct |
20 |
Correct |
157 ms |
16744 KB |
Output is correct |
21 |
Correct |
147 ms |
17132 KB |
Output is correct |
22 |
Correct |
129 ms |
16744 KB |
Output is correct |
23 |
Correct |
131 ms |
16712 KB |
Output is correct |
24 |
Correct |
124 ms |
16236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5248 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
5248 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5248 KB |
Output is correct |
9 |
Correct |
7 ms |
5248 KB |
Output is correct |
10 |
Correct |
9 ms |
5248 KB |
Output is correct |
11 |
Correct |
8 ms |
5120 KB |
Output is correct |
12 |
Correct |
8 ms |
5248 KB |
Output is correct |
13 |
Correct |
7 ms |
5248 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
8 ms |
5120 KB |
Output is correct |
16 |
Correct |
7 ms |
5112 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
8 ms |
5120 KB |
Output is correct |
22 |
Correct |
7 ms |
5240 KB |
Output is correct |
23 |
Correct |
7 ms |
5120 KB |
Output is correct |
24 |
Correct |
7 ms |
5120 KB |
Output is correct |
25 |
Correct |
104 ms |
10852 KB |
Output is correct |
26 |
Correct |
42 ms |
9536 KB |
Output is correct |
27 |
Correct |
161 ms |
14732 KB |
Output is correct |
28 |
Correct |
162 ms |
14560 KB |
Output is correct |
29 |
Correct |
106 ms |
10976 KB |
Output is correct |
30 |
Correct |
114 ms |
12132 KB |
Output is correct |
31 |
Correct |
147 ms |
11740 KB |
Output is correct |
32 |
Correct |
229 ms |
14556 KB |
Output is correct |
33 |
Correct |
188 ms |
12508 KB |
Output is correct |
34 |
Correct |
121 ms |
10836 KB |
Output is correct |
35 |
Correct |
181 ms |
13020 KB |
Output is correct |
36 |
Correct |
163 ms |
14608 KB |
Output is correct |
37 |
Correct |
84 ms |
9192 KB |
Output is correct |
38 |
Correct |
133 ms |
11100 KB |
Output is correct |
39 |
Correct |
31 ms |
6224 KB |
Output is correct |
40 |
Correct |
134 ms |
11216 KB |
Output is correct |
41 |
Correct |
124 ms |
10472 KB |
Output is correct |
42 |
Correct |
194 ms |
11184 KB |
Output is correct |
43 |
Correct |
80 ms |
7924 KB |
Output is correct |
44 |
Correct |
163 ms |
11184 KB |
Output is correct |
45 |
Correct |
33 ms |
6768 KB |
Output is correct |
46 |
Correct |
140 ms |
11244 KB |
Output is correct |
47 |
Correct |
40 ms |
7016 KB |
Output is correct |
48 |
Correct |
132 ms |
11172 KB |
Output is correct |
49 |
Correct |
196 ms |
16436 KB |
Output is correct |
50 |
Correct |
231 ms |
17616 KB |
Output is correct |
51 |
Correct |
150 ms |
14400 KB |
Output is correct |
52 |
Correct |
215 ms |
17660 KB |
Output is correct |
53 |
Correct |
97 ms |
11500 KB |
Output is correct |
54 |
Correct |
217 ms |
17636 KB |
Output is correct |
55 |
Correct |
200 ms |
16316 KB |
Output is correct |
56 |
Correct |
222 ms |
17636 KB |
Output is correct |
57 |
Correct |
36 ms |
7536 KB |
Output is correct |
58 |
Correct |
241 ms |
17592 KB |
Output is correct |
59 |
Correct |
134 ms |
13292 KB |
Output is correct |
60 |
Correct |
251 ms |
17772 KB |
Output is correct |
61 |
Correct |
130 ms |
17128 KB |
Output is correct |
62 |
Correct |
134 ms |
16912 KB |
Output is correct |
63 |
Correct |
123 ms |
16616 KB |
Output is correct |
64 |
Correct |
125 ms |
16360 KB |
Output is correct |
65 |
Correct |
142 ms |
17292 KB |
Output is correct |
66 |
Correct |
145 ms |
16360 KB |
Output is correct |
67 |
Correct |
145 ms |
16616 KB |
Output is correct |
68 |
Correct |
157 ms |
16744 KB |
Output is correct |
69 |
Correct |
147 ms |
17132 KB |
Output is correct |
70 |
Correct |
129 ms |
16744 KB |
Output is correct |
71 |
Correct |
131 ms |
16712 KB |
Output is correct |
72 |
Correct |
124 ms |
16236 KB |
Output is correct |
73 |
Execution timed out |
3032 ms |
16356 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |