Submission #1145160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145160		tnt	Trampoline (info1cup20_trampoline)	C++20	0 / 100	117 ms	3744 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 sort(all(v)) sort(v.begin(),v.end())

int mod = 998244353;
const int N = 3000 + 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 a[N][N];
signed main(){
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    int r,c,n;
    cin >> r >> c  >> n;
    vector <int> v,v1;
    vector  <pair<int,int>> q;
    for(int i = 1; i <= n; i++){
        int x,y;
        cin >> x >> y;
        v.pb(x),v1.pb(y);
        q.pb({x,y});
    }
    sort(v.begin(),v.end());
    sort(v1.begin(),v1.end());
    for(int i = 0; i < n; i++){
        int x = lower_bound(v.begin(),v.end(),q[i].first) - v.begin();
        int y = lower_bound(v1.begin(),v1.end(),q[i].second) - v1.begin();
        a[x][y] = 1;
    }
    int t;
    cin >> t;
    while(t--){
        int x,y,x1,y1;
        cin >> x >> y >> x1 >> y1;
        v.pb(x),v.pb(x1),v1.pb(y),v1.pb(y1);
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        sort(v1.begin(),v1.end());
        v1.erase(unique(v1.begin(), v1.end()), v1.end());
        x = lower_bound(v.begin(),v.end(),x) - v.begin();
        x1 = lower_bound(v.begin(),v.end(),x1) - v.begin();
        y = lower_bound(v1.begin(),v1.end(),y) - v1.begin();
        y1 = lower_bound(v1.begin(),v1.end(),y1) - v1.begin();
        bool f = 0;
        if(x == x1){
            cout << "Yes\n";
            continue;
        }
        while(true){
            while(y <= y1 && a[x][y] != 1){
                y++;
            }
            if(y > y1){
                f = 1;
                break;
            }
            x++;
            if(x == x1){
                break;
            }
            else if(x > x1){
                f = 1;
                break;
            }
        }
        if(f == 0) cout << "Yes\n";
        else cout << "No\n";
    }
    
}

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