oj.uz

답안 #687616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
687616 2023-01-26T16:10:16 Z Rares Trampoline (info1cup20_trampoline) C++14
43 / 100
 864 ms 28772 KB 
#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()
{
    cin >>n>>m>>q;
    for (int i=1;i<=q;++i){
        cin >>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;
    cin >>t;
    for (int i=1;i<=t;++i){
        int x1,x2,y1,y2;
        cin >>x1>>y1>>x2>>y2;
        if (x2==x1){
            cout <<"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){
            cout <<"No"<<'\n';
            rez.push_back (0);
            continue;
        }

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

        if (y1>v[dr1].c){
            cout <<"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){
            cout <<"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){
                cout <<"No"<<'\n';
                rez.push_back (0);
            }
            else{
                if (ok==0){
                    rez.push_back (1);
                    cout <<"Yes"<<'\n';
                }

                else{
                    rez.push_back (0);
                    cout <<"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
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 724 KB 200 token(s): yes count is 21, no count is 179
2 Correct 6 ms 724 KB 200 token(s): yes count is 70, no count is 130
3 Correct 4 ms 596 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 10756 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 127 ms 10728 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 120 ms 11272 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 128 ms 13412 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 742 ms 19036 KB expected NO, found YES [1st token]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 844 KB expected NO, found YES [16th token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 864 ms 28772 KB expected NO, found YES [54671st token]
2 Halted 0 ms 0 KB -