Submission #885371

#TimeUsernameProblemLanguageResultExecution timeMemory
885371TurcavidTrampoline (info1cup20_trampoline)C++14
0 / 100
479 ms38388 KiB
#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; 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:77: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]
   77 |                 if(p == v[l0].size())
      |                    ~~^~~~~~~~~~~~~~~
trampoline.cpp:122: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]
  122 |         if(a == v[x0].size() || b == -1)
      |            ~~^~~~~~~~~~~~~~~
trampoline.cpp:57:9: warning: unused variable 'x' [-Wunused-variable]
   57 |     int x=0;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...