Submission #675352

#TimeUsernameProblemLanguageResultExecution timeMemory
675352Hiennoob123Trampoline (info1cup20_trampoline)C++14
0 / 100
1126 ms132628 KiB
//#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx,avx2,fma,sse4.2") #include<bits/stdc++.h> #define ll long long #define int long long #define ii __int128 #define ld long double #define cd complex<ld> #define pll pair<int,int> #define pii pair<int,int> #define pld pair<ld,ld> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; ll r, c, n, cur, q; vector<pll> pt; vector<ll> nen; map<ll,ll> M; vector<pll> L[400005]; vector<ll> T[200005]; ll bin[21][200005]; void dfs(ll v,ll par) { bin[0][v] = par; for(int i = 1;i <= 20; i++) { ll x = bin[i-1][v]; bin[i][v] = bin[i-1][x]; } for(auto u: T[v]) { if(u==par) continue; dfs(u, v); } } void solve() { cin >> r >> c >> n; for(int i = 1; i<=n ; i++) { ll a, b; cin >> a >> b; pt.push_back(mp(a,b)); //pt.push_back(mp(a+1,b)); nen.push_back(a); nen.push_back(a+1); } sort(nen.begin(),nen.end()); cur = 1; M[nen[0]] = 1; for(int i = 1; i< nen.size(); i++) { if(nen[i]!=nen[i-1]) cur++; M[nen[i]] = cur; } for(int i = 0; i<n ;i++) { //cout << pt[i].fi << " "; pt[i].fi = M[pt[i].fi]; //cout << pt[i].fi << "\n"; L[pt[i].fi].push_back(mp(pt[i].se, i+1)); } for(int i = 400000; i>= 1; i--) { sort(L[i].begin(),L[i].end()); ll sz = L[i].size(); for(int j = 0;j < sz; j++) { //cout << i << " " << j << "\n"; if(j==sz-1) { vector<pll>::iterator it = lower_bound(L[i+1].begin(),L[i+1].end(),mp(L[i][j].fi, 0ll)); //cout << -1; //cout << "-1"; if(it==L[i+1].end()) { T[L[i][j].se].push_back(0); T[0].push_back(L[i][j].se); } else { pll a = *it; T[L[i][j].se].push_back(a.se); T[a.se].push_back(L[i][j].se); } //cout << -1; } else { vector<pll>::iterator it = lower_bound(L[i+1].begin(),L[i+1].end(),mp(L[i][j].fi, 0ll)); if(it==L[i+1].end()) { T[L[i][j].se].push_back(L[i][j+1].se); T[L[i][j+1].se].push_back(L[i][j].se); } else { pll a = *it; if(L[i][j+1].fi<=a.fi) { T[L[i][j].se].push_back(L[i][j+1].se); T[L[i][j+1].se].push_back(L[i][j].se); } else { T[L[i][j].se].push_back(a.se); T[a.se].push_back(L[i][j].se); } } } } } dfs(0, 0); cin >> q; for(int xx = 1; xx <= q; xx++) { ll a, b, u, v; cin >> a >> b >> u >> v; if(a==u&&b<=v) { cout << "Yes\n"; continue; } else if(a==u) { if(xx==1) assert(0); cout << "No\n"; continue; } a = M[a]; u = M[u]; if(u==0) { if(xx==1) assert(0); cout << "No\n"; continue; } vector<pll>::iterator it = lower_bound(L[a].begin(),L[a].end(),mp(b,0ll)); if(it==L[a].end()) { if(xx==1) assert(0); cout << "No\n"; continue; } pll p = *it; ll x = p.se; //cout << x << " " << u << '\n'; for(int i = 20; i>=0 ; i--) { if(bin[i][x]==0||pt[bin[i][x]-1].fi>=u) continue; //cout << x << " " << i << " " << pt[bin[i][x]-1].fi << "\n"; x = bin[i][x]; } //cout << pt[x-1].fi << "\n"; while(x!=0&&pt[x-1].fi<u-1) x = bin[0][x]; if(pt[x-1].fi!=u-1) { if(xx==1) assert(0); cout << "No\n"; continue; } else if(x==0) { if(xx==1) assert(0); cout << "No\n"; } else { if(pt[x-1].se<=v) { cout << "Yes\n"; } else cout << "No\n"; } } } signed main() { ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr); int t = 1;// cin >> t; //cout << -1; while(t--) { solve(); cout << "\n"; } }

Compilation message (stderr)

trampoline.cpp: In function 'void solve()':
trampoline.cpp:53:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 1; i< nen.size(); i++)
      |                    ~^~~~~~~~~~~~
#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...