Natasha a descoperit un nou joc pe calculator. Pe un suport se află N biluțe pe care este scris câte un număr s_i . Jocul constă în alegerea unei biluțe, biluță care se va ridica de pe suport și va pluti în aer pentru s_i secunde, apoi se va așeza din nou pe poziția ei în suport. În momentul în care o biluță atinge suportul, prima biluță b_st din stânga ei și prima biluță b_dr din dreapta ei (care nu s-au așezat pe suport în același moment de timp) se vor ridica în aer, fiecare plutind pentru s_st , respectiv s_dr secunde, după care se vor reașeza în suport, fiecare pe poziția ei. Această mișcare a biluțelor continuă până când Natasha se plictisește și închide calculatorul. Dar asta nu e tot. În timp ce Natasha urmărește mișcarea biluțelor, ea trebuie să răspundă la M întrebări de forma: “Este biluța b_k la momentul de timp t_k pe suport sau în aer?”.

Cerință

Pentru fiecare din cele M întrebări, răspundeți cu 1 dacă biluța b este pe suport, sau cu 0 dacă biluța este în aer.

Date de intrare

Fișierul de intrare bilute.in conține pe prima linie N, M si P reprezentând numărul de biluțe, numărul întrebărilor, respectiv indicele biluței pe care Natasha o alege la începutul jocului. Pe a doua linie se află N numere, reprezentând timpul, în secunde, de plutire a fiecărei biluțe. Pe următoarele M linii, se vor afla câte două numere, b_k si t_k , cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire biluțe.out va conține pe fiecare linie 0 sau 1, răspunsul la intrebări, în ordinea din fișierul de intrare.

Restricții și precizări

1 ≤ N, M ≤ 100 000
1 ≤ si, tk ≤ 200 000
1 ≤ bk, P ≤ N
Momentul t=0 este considerat atunci când prima biluță (cea aleasă de Natasha) atinge suportul.
Dacă la momentul t o biluță atinge suportul, ea se mai poate ridica în aer începând cu momentul t+1, iar la momentul t se consideră că biluța este pe suport.
Dacă la momentul t o biluță se ridică în aer, se consideră că la momentul t biluța este în aer.
Se garantează ca numarul total de plutiri a biluțelor nu va depăși 200 000.
Pentru 50% din teste N ≤ 200.

Exemplu

bilute.in

bilute.out

Explicații

La momentul 0 ajunge pe suport biluța 3 și va face să sară bilele 2 si 4. La momentul 3 biluța 2 ajunge pe suport și va face să plutească biluța 1 si 3, iar biluța 4 ajunge pe suport la momentul 4 și va face să plutească biluța 2 si 5. La momentul 5 ajunge pe suport biluța 3.

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

//bilute 100p
//autor: login
# include <iostream>
# include <fstream>
# include <queue>
# include <vector>
# include <algorithm>
# include <cassert>
# define DIM 100003
# define fs first
# define sc second
# define mp make_pair
# define pb push_back
using namespace std;
int n, m, pb, v[DIM], a[4*DIM], p[DIM], down[DIM], up[DIM], r[DIM];
vector< pair<int,pair<int,int> > >Q;
priority_queue< pair<int,int> >T;

void read ()
{
    ifstream fin ("bilute.in");
    fin>>n>>m>>pb;
    
    assert(n>0 && n<=100000);
    assert(m>0 && m<=100000);
    assert(pb>0 && pb<=n);
    
    for(int i=1;i<=n;++i)
    {
        fin>>v[i];
        
        assert(v[i]>0 && v[i]<200000);
    }
    for(int i=1;i<=m;++i)
    {
        int b, t;
        fin>>b>>t;
        
        assert(b>0 && b<=n);
        assert(t>0 && t<200000);
        
        Q.pb(mp(t, mp(b, i)));
    }
}

void upd(int k, int st, int dr, int p, int v)
{
    if (st==dr)
    {
        a[k]=v;
        return;
    }
    
    int mij = (st+dr)/2;
    if (p<=mij)
        upd(2*k, st, mij, p, v);
    else
        upd(2*k+1, mij+1, dr, p, v);
    
    a[k]=a[2*k]+a[2*k+1];
}

int querySum(int k, int st, int dr, int i, int j)
{
    if (st==dr)
        return a[k];
    
    int mij=(st+dr)/2, x=0, y=0;
    if (i<=mij)x = querySum(2*k, st, mij, i, j);
    if (j>mij)y = querySum(2*k+1, mij+1, dr, i, j);
    
    return x+y;
}

int queryPoz(int k, int st, int dr, int s)
{
    if (st==dr)
    {
        if (a[k])
            return st;
        return 0;
    }
        
    int mij=(st+dr)/2;
    
    if (a[2*k]<s)return queryPoz(2*k+1, mij+1, dr, s-a[2*k]);
    return queryPoz(2*k, st, mij, s);
}

void solve ()
{
    sort(Q.begin(),Q.end());
    for(int i=1;i<=n;++i)
    {
        upd(1, 1, n, i, 1);
        p[i]=1;
    }
    
    T.push(mp(0, pb));
    p[pb]=0;
    upd(1, 1, n, pb, 0);
    
    int q = 0, t, k, sp, bst, bdr;
    while(q<m)
    {
        t = -T.top().fs;
        
        while(q<m && Q[q].fs<t)
        {
            r[Q[q].sc.sc] = p[Q[q].sc.fs];
            ++q;
        }
        
        while(T.size() && -T.top().fs == t)
        {
            k = T.top().sc;
            T.pop();
            
            sp = querySum(1, 1, n, 1, k);
            bst = queryPoz(1, 1, n, sp);
            bdr = queryPoz(1, 1, n, sp+1);
            
            if(bst)
            {
                up[++up[0]]=bst;
                p[bst] = 0;
                upd(1, 1, n, bst, 0);
            }
            if (bdr)
            {
                up[++up[0]]=bdr;
                p[bdr] = 0;
                upd(1, 1, n, bdr, 0);
            }
            down[++down[0]] = k;
        }
        
        while(down[0])
        {           
            upd(1, 1, n, down[down[0]], 1);
            p[down[down[0]]]=1; // 1 = pamant
            --down[0];
        }
        
        while(up[0])
        {
            T.push(mp(-t-v[up[up[0]]], up[up[0]]));
            --up[0];
        }
    }
}

int main()
{
    read();
    solve();
    
    freopen("bilute.out", "w", stdout);
    for(int i=1;i<=m;++i)
        printf("%d
", r[i]);
    
    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 #145 bilute

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