Rezolvare completă PbInfo #2035 Empowermage

Este cunoscut faptul că unul din cele mai vechi concursuri existene (poate cel mai vechi) este un concurs numit EMPOWERMAGE, unde vrăjitori din toată lumea vin să concureze pentru a câștiga titlul de vrăjitorul anului. În fiecare an, pionierul acestui concurs, vrăjitorul Arpsod, a ținut cont câți participanți au concurat. Din cauza trecerii timpului, de pe pergamentele cu statistica referitoare la numărul de participanți, au mai rămas vizibili doar N ani.
Știind ce ani mai sunt încă vizibili și câți participanți au fost în fiecare dintre acești ani, vi se cere să răspundeți la mai multe afirmații de forma: “Anul Y a avut cei mai mulți participanți de la anul X incoace”.
Răspunsul poate fi de 3 feluri: ADEVARAT, FALS, POATE

Răspunsul este considerat adevărat dacă: - Numărul de participanți pentru anii X și Y cât și pentru toți anii dintre ei este cunoscut. - Numărul de participanți din anul Y a fost cel mult egal cu numărul de participanți din anul X. - Pentru toți anii intermediari Z (X < Z < Y), număru de participanți a fost strict mai mic decât în anul Y

Răspunsul este POATE dacă sunt îndeplinite condițiile de mai sus (mai puțin prima) dar nu avem informații despre anumiți ani care ne interesează.
Răspunsul este FALS dacă nu este nici ADEVARAT nici POATE.

Cerința

Cunoscând numărul de ani vizibili și numărul de participanți din fiecare din acești ani, să se răspundă la mai multe afirmații de tipul enunțat mai sus.

Date de intrare

Pe prima linie a fișierului empowermage.in se va afla numărul natural N, reprezentând numărul de ani vizibili. Urmează apoi N linii a câte 2 valori separate prin spațiu: ai pi cu semnificația că în anul ai au participat pi participanți. Pe linia N+2 se află numărul natural M, reprezentând numărul de afirmații la care trebuie să răspundeți. Urmează apoi M linii a câte două valori: X Y ce codifică afirmația “Anul Y a avut cei mai mulți participanți de la anul X incoace”.

Date de ieșire

Fișierul empowermage.out va conține M linii, pe linia i fiind răspunsul la afirmația i. Răspunsul poate fi ADEVARAT, FALS sau POATE (CU MAJUSCULE)

Restricții și precizări

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 10.000
  • -109 ≤ an ≤ 109
  • 1 ≤ participanti dintr-un an ≤ 109
  • -109 ≤ X < Y ≤ 109
  • Cei N ani sunt dați în ordine cronologică

Exemplu

empowermage.in

4
2002 4920
2003 5901
2004 2832
2005 3890
2
2002 2005
2003 2005
3
1985 5782
1995 3048
2005 4890
2
1985 2005
2005 2015

empowermage.out

FALS
ADEVARAT
POATE
POATE

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Empowermage:

// implementare: Cristi Dospra
// punctaj: 100p
// complexitate: O(N + MlogN)

#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <climits>
using namespace std;

#define NMAX 50002

ifstream fin("empowermage.in");
ofstream fout("empowermage.out");

int pred[NMAX], urm[NMAX];

stack<int> stiva;
vector <pair<int, int> > v;

int N, M;
int cautbin(int x) {

    int st = 1, dr = N;
    int mid;

    while (st <= dr) {

        mid = (st + dr) >> 1;

        if (v[mid].first == x)
            return mid;

        if (v[mid].first < x)
            st = mid + 1;
        else
            dr = mid - 1;
    }

    return -1;
}


int main() {


    fin >> N;

    v.resize(N + 2);

    v[0] = make_pair(INT_MIN, INT_MAX);
    stiva.push(0);

    for (int i = 1; i <= N; ++i) {
        fin >> v[i].first >> v[i].second;

        while (!stiva.empty() && v[i].second > v[stiva.top()].second)
            stiva.pop();

        pred[i] = min(i, stiva.top());
        stiva.push(i);
    }

    while (stiva.size() > 0)
        stiva.pop();

    v[N+1] = make_pair(INT_MAX, INT_MAX);
    stiva.push(N + 1);
    for (int i = N; i >= 1; --i) {

        while (!stiva.empty() && v[i].second > v[stiva.top()].second)
            stiva.pop();

        urm[i] = stiva.top();
        stiva.push(i);
    }

    fin >> M;

    int x, y;
    while (M--) {
        fin >> x >> y;

        int pozx = cautbin(x);
        int pozy = cautbin(y);

        if (pozx != -1 && pozy != -1) {

            if (pred[pozy] != pozx) {
                fout << "FALS\n";
                continue;
            }

            if (pozy - pozx == y - x) {
                fout << "ADEVARAT\n";
                continue;
            }

            fout << "POATE\n";
        }
        else if (pozy != -1) {

            if (v[pred[pozy]].first > x)
                fout << "FALS\n";
            else
                fout << "POATE\n";
        }
        else if (pozx != -1) {

            if (v[urm[pozx]].first < y)
                fout << "FALS\n";
            else
                fout << "POATE\n";
        }
        else {
            fout << "POATE\n";
        }
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2035 Empowermage

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2035 Empowermage de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!