În Bistriţa sunt N copii, fiecare dintre ei având un număr preferat X_i . Copii se aşează pe un rând, cu poziţiile numerotate de la 1 la N. După ce copii s-au aşezat, profesoara de educaţie fizică le cere să execute M mişcări de tipul (a, b), cu semnificaţia că îşi vor schimba ordinea copiii care se află între poziţiile a şi b, inclusiv.

Cerință

Să se răspundă la Q întrebări de tipul p, cu semnificaţia: care este numărul preferat al copilului, care se află pe poziţia p, după executarea mişcărilor cerute de profesoara de educaţie fizică.

Date de intrare

Fișierul copii.in are pe prima linie un număr natural N. Pe linia a 2-a sunt N numere X_i , separate prin câte un spațiu, cu semnificaţia din enunţ. Pe linia a 3-a este numărul M. Pe următoarele M linii se găseșc câte un două numere a şi b cu semnificația de mai sus. Pe următoarea linie se află numărul Q. Pe următoarele linii se află câte un număr p, cu semnificaţia de mai sus.

Date de ieșire

Fișierul copii.out va conține Q linii. Pe fiecare linie se va afla răspunsul la întrebarea respectivă din fişierul de intrare

Restricții

1 ≤ N ≤ 100.000
1 ≤ M ≤ 10.000
1 ≤ Q ≤ 100
1 ≤ a ≤ b ≤ N
-2.000.000.000 ≤ X_i ≤ 2.000.000.000

Exemplu

copii.in

10
1 2 3 4 5 6 7 8 9 10
2
2 5
4 8
6
1
2
4
5
8
10

copii.out

Explicaţie

După prima mişcare şirul format din numerele preferate ale copiilor devine: 1 5 4 3 2 6 7 8 9 10.

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 copii:

//Code by Patcas Csaba

//Time complexity: O(q * m)

//Space complexity: O(n + m)

//Method: Ad hoc

//Implementation time:  7 minutes



#include <vector>

#include <string> 

#include <set> 

#include <map> 

#include <queue> 

#include <bitset> 

#include <stack>

#include <list>



#include <numeric> 

#include <algorithm> 



#include <cstdio>

#include <fstream>

#include <iostream> 

#include <sstream> 

#include <iomanip>



#include <cctype>

#include <cmath> 

#include <ctime>

#include <cassert>



using namespace std;



#define LL long long

#define PII pair <int, int>

#define VB vector <bool>

#define VI vector <int>

#define VD vector <double>

#define VS vector <string>

#define VPII vector <pair <int, int> >

#define VVI vector < VI >

#define VVB vector < VB >



#define FORN(i, n) for(int i = 0; i < (n); ++i)

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)

#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define FORI(it, X) for(__typeof((X).begin()) it = (X).begin(); it !=(X).end(); ++it) 

#define REPEAT do{ 

#define UNTIL(x) }while(!(x)); 



#define SZ size()

#define BG begin() 

#define EN end() 

#define CL clear()

#define X first

#define Y second

#define RS resize

#define PB push_back

#define MP make_pair

#define ALL(x) x.begin(), x.end()



#define IN_FILE "copii.in"

#define OUT_FILE "copii.out"



ifstream fin(IN_FILE);

ofstream fout(OUT_FILE);



int n, m, q;

VI a;

vector <PII> updates;



int main()

{

    //Read data

    fin >> n;

    a.RS(n + 1);

    FOR(i, 1, n) fin >> a[i];

    fin >> m;

    updates.RS(m + 1);

    FOR(i, 1, m)

    {

        int x, y;

        fin >> x >> y;

        updates[i] = MP(x, y);

    }

    fin >> q;

    FORN(i, q)

    {

        int p;

        fin >> p;

        FORD(j, m, 1)

        {

            int x = updates[j].X, y = updates[j].Y;

            if (x <= p && p <= y) p = x + (y - p);

        }

        fout << a[p] << endl;

    }

    fin.close();



    //Solve



    //Write data

    fout.close();



    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 #144 copii

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #144 copii 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!

Rezolvare completă PbInfo #144 copii