Submission #687613

#	Time	Username	Problem	Language	Result	Execution time	Memory
687613		Rares	Trampoline (info1cup20_trampoline)	C++14	0 / 100	2084 ms	212 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("trampoline.in");
ofstream fout ("trampoline.out");

const int MAXN=200010;
const int LGMAX=21;

int n,m,q;
int urm[LGMAX][MAXN];
vector <int> rez;

struct tramp{
    int l,c,pos,nr;
}v[MAXN];
bool comp (tramp a, tramp b){
    if (a.l==b.l)
        return a.c<b.c;
    return a.l<b.l;
}

int main()
{
    fin >>n>>m>>q;
    for (int i=1;i<=q;++i){
        fin >>v[i].l>>v[i].c;
        v[i].pos=i;
    }
    sort (v+1,v+q+1,comp);
    for (int i=1;i<=n;++i){

    }
    v[q].nr=1;
    for (int i=q-1;i>=1;--i){
        if (v[i].l==v[i+1].l)
            v[i].nr=v[i+1].nr+1;
        else
            v[i].nr=1;
    }
    //gasim fiul fiecarei trambulini verzi, adica prima la dreapta de pe linia imediat urmatoare
    for (int i=1;i<=q;++i){
        if (i+v[i].nr+v[i+v[i].nr].nr-1>q)
            continue;
        if (v[i+v[i].nr].l!=v[i].l+1)
            continue;
        int st=i+v[i].nr,dr=i+v[i].nr+v[i+v[i].nr].nr-1,drk=dr;
        while (st<=dr){
            int mij=(st+dr)/2;
            if (v[mij].c>=v[i].c){
                dr=mij-1;
            }
            else{
                st=mij+1;
            }
        }
        if (st>drk)
            continue;
        urm[0][i]=st;
    }
    //construim fiul din puteri ale lui 2, asemanator cu rmq
    for (int i=1;i<LGMAX;++i){
        for (int j=1;j<=q;++j){
            if (urm[i-1][urm[i-1][j]]!=0)
                urm[i][j]=urm[i-1][urm[i-1][j]];
        }
    }


    int t;
    fin >>t;
    for (int i=1;i<=t;++i){
        int x1,x2,y1,y2;
        fin >>x1>>y1>>x2>>y2;
        if (x2==x1){
            fout <<"Yes"<<'\n';
            rez.push_back (1);
            continue;
        }
        int st=1,dr=q;
        if (x1<v[1].l or x2>v[q].l+1){
            continue;
        }
        while (st<=dr){
            int mij=(st+dr)/2;
            if (v[mij].l>=x1)
                dr=mij-1;
            else
                st=mij+1;
        }
        //cout <<st<<'\n';

        if (v[st].l!=x1){
            fout <<"No"<<'\n';
            rez.push_back (0);
            continue;
        }

        int st1=st,dr1=st+v[st].nr-1;

        if (y1>v[dr1].c){
            fout <<"No"<<'\n';
            rez.push_back (0);
            continue;
        }

        while (st1<=dr1){
            int mij=(st1+dr1)/2;
            if (v[mij].c>=y1)
                dr1=mij-1;
            else
                st1=mij+1;
        }
        int dif=x2-x1-1;

        if (dif==0){
            fout <<"Yes"<<'\n';
            rez.push_back (1);
            continue;
        }
        else{
            int p=1,x=0,ok=0;
            //fout <<urm[0][3];
            while (dif){
                if ((dif&p)>0){
                    if (urm[x][st1]==0){
                        ok=1;
                        break;
                    }
                    else
                        st1=urm[x][st1];
                    dif-=p;
                }
                x++;
                p*=2;
            }
            //fout <<v[st1].l;
            if (v[st1].c>y2 or v[st1].l!=x2-1){
                fout <<"No"<<'\n';
                rez.push_back (0);
            }
            else{
                if (ok==0){
                    rez.push_back (1);
                    fout <<"Yes"<<'\n';
                }

                else{
                    rez.push_back (0);
                    fout <<"No"<<'\n';
                }

            }
        }
    }
    /*for (int i=1;i<=t;++i){
        int ok;
        string check1;
        fin >>check1;
        if (check1[0]=='Y')
            ok=1;
        else
            ok=0;
        if (ok!=rez[i-1]){
            fout <<"Nu e corect";
            return 0;
        }
    }*/
    //fout <<"Corect";
    return 0;
}
/*
5 5 5
1 1
1 3
2 2
4 4
5 5
5
1 1 2 5
2 3 2 5
3 1 4 5
2 1 5 5
4 3 5 3
*/

• Subtask 1: 0 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27