Submission #885373

#	Time	Username	Problem	Language	Result	Execution time	Memory
885373		Turcavid	Trampoline (info1cup20_trampoline)	C++14	0 / 100	456 ms	39004 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;

/*
fie a prima trambulina din dreapta lui start
si  b prima trambulina din stanga lui finish care sa se duca in sus
^ cautare binara

( caz special cand start si finish sunt pe aceeasi linie )

vrei sa stii daca poti sa ajungi de la a la b
faci precalculare ig:

precalculare: O(N*log(N))
verificare per query: O(log(N))
*/
map<int, vector<pair<int, int>>> v; // poz, indicele poz
int up[200005][35]; // binary lifting

int Find(vector<pair<int, int>>& vec, int p, bool left) // cautam prima trambulina cu poz >= p
{
    int st=-1, dr=vec.size();
    while(st+1 < dr)
    {
        int mid=(st+dr)/2;
        if((!left && vec[mid].first >= p) || (left && vec[mid].first > p))
            dr=mid;
        else
            st=mid;
    }
    if(left)
        dr--;
    return dr;
}

int post[200005]; // coloana fiecarei trambuline verzi, folosesc asta la sfarsit

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int r, c, n;
    cin>>r>>c>>n;
    for(int i=1; i<=n; i++)
    {
        int x, y;
        cin>>x>>y;
        post[i]=y;
        v[x].push_back({y, i});
    }
    for(auto &it:v)
    {
        sort(it.second.begin(), it.second.end());
    }
    // precalculare
    int x=0;
    for(auto &it:v)
    {
        vector<pair<int, int>>& vec=it.second;
        int l=it.first;
        for(pair<int, int>& pr:vec)
        {
            int u=pr.second;
            if(up[u][0])
            {
                continue;
            }
            int l0=l;
            int p=pr.first;
            int u0=u; // last u
            while(true)
            {
                l0++;
                p=Find(v[l0], post[u], false);
                //cout<<u<<'\n';
                if(p == v[l0].size())
                {
                    break;
                }
                u=v[l0][p].second;
                if(up[u][0])
                    break;
                up[u][0]=u0;
                p=v[l0][p].first;
                u0=u;
            }
        }
    }
    for(int k=1; k<32; k++)
    {
        for(int i=1; i<=n; i++)
        {
            up[i][k]=up[up[i][k-1]][k-1];
        }
    }

    //for(int i=1; i<=n; i++)
    //    cout<<up[i][0]<<" ";
    
    //return 0;
    // query-uri
    int t;
    cin>>t;
    for(int i=1; i<=t; i++)
    {
        int x0, y0, x1, y1;
        cin>>x0>>y0>>x1>>y1;
        if(x1 < x0 || y1 < y0)
        {
            cout<<"No\n";
            continue;
        }
        if(x0 == x1)
        {
            cout<<"Yes\n";
            continue;
        }
        x1--; // ca te uiti la trambulina de sus ( amongus reference )
        int a=Find(v[x0], y0, false);
        int b=Find(v[x1], y1, true);
        if(a == v[x0].size() || b == -1)
        {
            cout<<"No\n";
            continue;
        }
        //cout<<a<<" "<<b<<'\n';
        //continue;
        // acum cauti al x1-x0 lea ancestor la lui b
        int sus=x1-x0;
        for(int j=0; j<32; j++)
        {
            if(sus&(1<<j))
            {
                b=up[b][j];
            }
        }
        if(post[b] >= post[a])
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}

Compilation message (stderr)

trampoline.cpp: In function 'int32_t main()':
trampoline.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 if(p == v[l0].size())
      |                    ~~^~~~~~~~~~~~~~~
trampoline.cpp:123:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if(a == v[x0].size() || b == -1)
      |            ~~^~~~~~~~~~~~~~~
trampoline.cpp:58:9: warning: unused variable 'x' [-Wunused-variable]
   58 |     int x=0;
      |         ^

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