oj.uz

Submission #679042

# Submission time Handle Problem Language Result Execution time Memory
679042 2023-01-07T09:45:02 Z alexdd Trampoline (info1cup20_trampoline) C++17
100 / 100
 1275 ms 85448 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int r,c,n;
int a[200001];
int b[200001];
vector<pair<int,int>> lin[1200005];
int anc[200001][19];
map<int,int> mapl;
map<int,int> norml;
int cntn=0;
void normalizare()
{
    for(int i=1;i<=n;i++)
    {
        mapl[a[i]]++;
        mapl[a[i]-1]++;
        mapl[a[i]+1]++;
    }
    int val;
    for(auto it:mapl)
    {
        cntn++;
        norml[it.first]=cntn;
    }
    for(int i=1;i<=n;i++)
        a[i]=norml[a[i]];
}
bool query(int lins, int cols, int linf, int colf)
{
    ///returneaza colf
    if(lins>linf)
        return 0;
    if(cols>colf)
        return 0;
    if(lins==linf)
        return 1;

    if(lin[lins].size()==0 || lin[lins][lin[lins].size()-1].first < cols)
        return 0;
    int st,dr,mij;
    st=0;
    dr=lin[lins].size()-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(lin[lins][mij].first>=cols && (mij==0 || lin[lins][mij-1].first<cols))
            break;
        else if(lin[lins][mij].first>=cols)
            dr=mij-1;
        else
            st=mij+1;
    }
    int cur = lin[lins][mij].second;
    for(int i=0;i<19;i++)
    {
        if(((1<<i)&(linf-lins-1))!=0)
            cur = anc[cur][i];
        if(cur==-1)
            break;
    }
    if(cur==-1)
        return 0;
    if(b[cur] <= colf)
        return 1;
    else
        return 0;
}
int cit[200001][4];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>r>>c>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>cit[i][0]>>cit[i][1]>>cit[i][2]>>cit[i][3];
        mapl[cit[i][0]]++;
        mapl[cit[i][0]-1]++;
        mapl[cit[i][0]+1]++;
        mapl[cit[i][2]]++;
        mapl[cit[i][2]-1]++;
        mapl[cit[i][2]+1]++;
    }
    normalizare();
    for(int i=1;i<=n;i++)
    {
        lin[a[i]].push_back({b[i],i});
    }
    for(int i=1;i<=cntn;i++)
        sort(lin[i].begin(),lin[i].end());
    for(int i=1;i<=cntn;i++)
    {
        for(auto x:lin[i])
        {
            ///calc anc[x.second][0]
            if(lin[i+1].size()==0 || lin[i+1][lin[i+1].size()-1].first<x.first)
            {
                anc[x.second][0]=-1;
            }
            else
            {
                int st,dr,mij;
                st=0;
                dr=lin[i+1].size()-1;
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(lin[i+1][mij].first>=x.first && (mij==0 || lin[i+1][mij-1].first<x.first))
                        break;
                    else if(lin[i+1][mij].first>=x.first)
                        dr=mij-1;
                    else
                        st=mij+1;
                }
                anc[x.second][0] = lin[i+1][mij].second;
            }
        }
    }
    for(int put=1;put<19;put++)
    {
        for(int i=1;i<=cntn;i++)
        {
            for(auto x:lin[i])
            {
                ///calc anc[x.second][put]
                if(anc[x.second][put-1]==-1)
                    anc[x.second][put]=-1;
                else
                    anc[x.second][put]=anc[anc[x.second][put-1]][put-1];
            }
        }
    }
    int lins,cols,linf,colf;
    for(int i=0;i<q;i++)
    {
        lins = norml[cit[i][0]];
        cols = cit[i][1];
        linf = norml[cit[i][2]];
        colf = cit[i][3];
        if(query(lins,cols,linf,colf))
            cout<<"Yes";
        else
            cout<<"No";
        cout<<"\n";
    }
    return 0;
}

Compilation message

trampoline.cpp: In function 'void normalizare()':
trampoline.cpp:20:9: warning: unused variable 'val' [-Wunused-variable]
   20 |     int val;
      |         ^~~
trampoline.cpp: In function 'bool query(int, int, int, int)':
trampoline.cpp:54:28: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     int cur = lin[lins][mij].second;
      |                            ^
trampoline.cpp: In function 'int main()':
trampoline.cpp:120:48: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |                 anc[x.second][0] = lin[i+1][mij].second;
      |                                                ^

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29396 KB 200 token(s): yes count is 21, no count is 179
2 Correct 21 ms 29448 KB 200 token(s): yes count is 70, no count is 130
3 Correct 19 ms 29268 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 47924 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 174 ms 49868 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 152 ms 48840 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 174 ms 49876 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 50976 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 257 ms 62468 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 284 ms 62796 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 385 ms 63132 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 377 ms 63156 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 642 ms 69964 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29012 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 21 ms 29380 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 31 ms 31072 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 19 ms 29300 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 25 ms 29424 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 22 ms 29304 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 59800 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 595 ms 65356 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 304 ms 62640 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 1275 ms 85448 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 583 ms 70248 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 295 ms 62692 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 293 ms 62792 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 276 ms 62524 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 793 ms 69896 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 784 ms 69984 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 1022 ms 77132 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 246 ms 62304 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 293 ms 62676 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 415 ms 63084 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 262 ms 62272 KB 200000 token(s): yes count is 129674, no count is 70326