Submission #987044

#TimeUsernameProblemLanguageResultExecution timeMemory
987044Zbyszek99Trampoline (info1cup20_trampoline)C++17
100 / 100
1991 ms206872 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ff first #define ss second #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define size(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace std; //mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll rand(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll pair_to_int(pair<int,int> a) { ll p = a.ff; ll p2 = a.ss; return p + p2*1000000005LL; } pair<int,int> int_to_pair(ll x) { ll p2 = x / 1000000005LL; ll p = x - p2*1000000005LL; swap(p2,p); return {p2,p}; } unordered_map<int, int> mapa; vector<int> pon[200001]; unordered_map<ll,ll> next_[19]; int find_next(int y, int x) { // cout << "finding " << y << " " << x << " \n"; int pocz = 0; int kon = size(pon[y])-1; int wyn = -1; while(pocz <= kon) { int srod = (pocz+kon)/2; if(pon[y][srod] >= x) { kon = srod-1; wyn = pon[y][srod]; } else { pocz = srod+1; } } return wyn; } void solve() { int R,C,n; cin >> R >> C >> n; vector<int> byly; vector<pair<int,int>> points; // cout << pair_to_int({2137,56}) << " " << int_to_pair(pair_to_int({2137,56})).ff << " " << int_to_pair(pair_to_int({2137,56})).ss << " xd\n"; rep(i,n) { int x,y; cin >>y >> x; if(mapa[y] == 0) mapa[y] = i+1; pon[mapa[y]].pb(x); points.pb({y,x}); } forall(it, mapa) sort(all(pon[it.ss])); int pop = -1; forall(it, mapa) { //cout << it.ff << " " << it.ss << " b\n"; if(it.ff != pop) byly.pb(it.ff); pop = it.ff; } sort(all(byly)); rep(i,size(byly)) { //cout << byly[i] << i << " " <<size(byly)-1 << " byly\n"; if(i == size(byly)-1 || byly[i] != byly[i+1]-1) { forall(it2,pon[mapa[byly[i]]]) { next_[0][pair_to_int({byly[i],it2})] = pair_to_int({byly[i],it2}); } } else { forall(it2,pon[mapa[byly[i]]]) { int iter = find_next(mapa[byly[i+1]],it2); if(iter != -1) { next_[0][pair_to_int({byly[i],it2})] = pair_to_int({byly[i+1],iter}); } else { next_[0][pair_to_int({byly[i],it2})] = pair_to_int({byly[i],it2}); } } } } rep2(k,1,18) { forall(it,points) { next_[k][pair_to_int(it)] = next_[k-1][next_[k-1][pair_to_int(it)]]; } } int q; cin >> q; rep(i,q) { int y1,x1,y2,x2; cin >> y1 >> x1 >> y2 >> x2; int odl = y2-y1-1; if(y2 < y1 || x2 < x1) { cout << "No\n"; continue; } if(y1 == y2) { cout << "Yes\n"; continue; } int aktpoint_iter = find_next(mapa[y1],x1); if(aktpoint_iter == -1) { cout << "No\n"; continue; } pair<int,int> aktpoint = {y1,aktpoint_iter}; rep(k,18) { // cout << aktpoint.ff << " " << aktpoint.ss << " " << next_[k][pair_to_int(aktpoint)] << " aktpoint\n"; if(odl & (1 << k)) { aktpoint = int_to_pair(next_[k][pair_to_int(aktpoint)]); } } if(aktpoint.ff == y2-1 && aktpoint.ss <= x2) { cout << "Yes\n"; } else { cout << "No\n"; } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); // random(); int t = 1; //cin >> t; while(t--) solve(); }
#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...