Submission #1145435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145435		tnt	Trampoline (info1cup20_trampoline)	C++20	42 / 100	2099 ms	285928 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back                    
#define ll long long
#define all(v) v.begin(),v.end()

int mod = 998244353;
const int N = 2e5 + 10;
const int inf = 1e9;
int fact[200001];
ll binpow(ll a, ll b){
 if(b == 0) return 1;
 else if(b % 2 == 1) return (a * binpow(a, b - 1)) % mod;
 ll p = binpow(a,b / 2);
 return (p * p) % mod;
}
int was[N],up[N][20];
vector <int> ord, v,sx,sy;
vector <int> g[N];
int x[N],y[N],x1[N],y2[N];
vector <pair <int,int> > mp[N];
void dfs(int u){
    for(int to : g[u]){
        if(was[to] == 1) continue;
        dfs(to);
    }
    ord.push_back(u);
}
bool func(int u, int l1, int r1){
    int k = l1 - x1[u] - 1;
    if (k >= (1 << 20)) return false;
    for(int i = 19; i >= 0; i--){
        if (k >> i & 1) u = up[u][i];
    }
    if(x1[u] == l1  - 1 && y2[u] <= r1){
        return true;
    }
    else return false;
}
signed main(){
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int r2,c,n;
    cin >> r2 >> c >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        sx.push_back(x[i]);
        sy.push_back(y[i]);
        x1[i] = x[i];
        y2[i] = y[i];
    }
    sort(all(sx)), sort(all(sy));
    sx.erase(unique(all(sx)), sx.end());
    sy.erase(unique(all(sy)), sy.end());
    for (int i = 1; i <= n; i++) {
        x[i] = lower_bound(all(sx), x[i]) - sx.begin();
        y[i] = lower_bound(all(sy), y[i]) - sy.begin();
        mp[x[i]].push_back({y[i], i});
    }
    for(int i = 0; i < N; i++) sort(all(mp[i]));
    for(int i = 1;i <= n; i++){
        int it = lower_bound(all(mp[x[i] + 1]), make_pair(y[i],0)) - mp[x[i] + 1].begin();
        if(it == mp[x[i] + 1].size() || x1[mp[x[i] + 1][it].second] - x1[i] != 1) continue;
        g[i].pb(mp[x[i] + 1][it].second);
    }
    for(int i = 1; i <= n; i++){
        if(was[i] != 1){
            dfs(i);
        }
    }
    for (int x: ord) {
        if (!g[x].size()) {
            for (int k = 0; k < 20; k++) {
                up[x][k] = x;
            }
            continue;
        }
        up[x][0] = g[x][0];
        for(int i = 1; i < 20; i++) up[x][i] = up[up[x][i - 1]][i - 1];
    }
    int t;
    cin >> t;
    while(t--){
        int l,r,l1,r1;
        cin >> l >> r >> l1 >> r1;
        if(r > r1){
            cout << "No\n";
            continue;
        }
        if(l1 == l){
            cout << "Yes\n";
            continue;
        }
        int it = lower_bound(all(sx),l) - sx.begin();
        if(it == sx.size() || l != sx[it]){
            cout << "No\n";
            continue;
        }
        r = lower_bound(all(sy), r) - sy.begin();
        int pos = lower_bound(all(mp[it]),make_pair(r,0)) - mp[it].begin();
        if (pos == mp[it].size()) {
            cout << "No\n";
            continue;
        }
        if(func(mp[it][pos].second,l1,r1)) cout << "Yes\n";
        else cout << "No\n";
    }
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 19 / 19
• Subtask 5: 0 / 27