Submission #675301

#TimeUsernameProblemLanguageResultExecution timeMemory
675301jahsdwaijsdTrampoline (info1cup20_trampoline)C++14
100 / 100
626 ms40924 KiB
/* #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") */ #include <bits/stdc++.h> #define taskname "bai3" #define all(x) x.begin(), x.end() #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> using namespace std; const int mxN = 2e5 + 5; const int base = 1e9 + 1; const int mod = 1e9 + 7; const ll oo = 1e18; int r, c, t, q, lg[mxN], pw[25]; int sparse_table[25][mxN]; vector<pii> v; map<int, vector<pii>> mp; bool sortbysec(const pii &a, const pii &b) { if(a.ss != b.ss) return (a.ss < b.ss); return (a.ff < b.ff); } void solve() { cin >> r >> c >> t; lg[1] = 0; pw[0] = 1; for(int i = 2; i < mxN; ++i) lg[i] = lg[i >> 1] + 1; for(int i = 1; i < 20; ++i) pw[i] = pw[i - 1] * 2; for(int i = 1; i <= t; ++i) { int u, v1; cin >> u >> v1; v.pb({u, v1}); } sort(all(v)); for(int i = 0; i < t; ++i) mp[v[i].ff].pb({v[i].ss, i}); sparse_table[0][t] = t; for(int i = 0; i < t; ++i) { if(mp.find(v[i].ff + 1) == mp.end()) { sparse_table[0][i] = t; continue; } auto it = lower_bound(all(mp[v[i].ff + 1]), make_pair(v[i].ss, 0)); if(it == mp[v[i].ff + 1].end()) sparse_table[0][i] = t; else sparse_table[0][i] = (*it).ss; } for(int i = 1; i < 20; ++i) { sparse_table[i][t] = t; for(int j = 0; j < t; ++j) { sparse_table[i][j] = sparse_table[i - 1][sparse_table[i - 1][j]]; } } cin >> q; while(q--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if(x1 > x2) { cout << "No\n"; continue; } if(x1 == x2) { if(y1 <= y2) { cout << "Yes\n"; } else cout << "No\n"; continue; } int dis = x2 - x1; if(dis > (int)mp.size()) { cout << "No\n"; continue; } if(mp.find(x1) == mp.end()) { cout << "No\n"; continue; } auto it = lower_bound(all(mp[x1]), make_pair(y1, 0)); if(it == mp[x1].end()) { cout << "No\n"; continue; } int st = (*it).ss; --dis; while(dis) { int tmp = lg[dis]; st = sparse_table[tmp][st]; dis -= pw[tmp]; } if(st == t) { cout << "No\n"; continue; } pii tmp1 = v[st]; if(tmp1.ss <= y2) { cout << "Yes\n"; } else cout << "No\n"; } } signed main() { #ifdef CDuongg freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }
#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...