제출 #1145045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145045		Robert_junior	Trampoline (info1cup20_trampoline)	C++20	11 / 100	762 ms	39516 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5 + 7;
int timer, x[N], y[N];
map<int, set<int>>mp;
map<pair<int, int>, int>comp;
void dfs(int x, int y){
    comp[{x, y}] = timer;
    if(mp[x - 1].size()){
        auto it = mp[x - 1].upper_bound(y);
        if(it != mp[x - 1].begin()){
            it--;
            if(!comp[{x - 1, *it}]) dfs(x - 1, *it);
        }
    }
    if(mp[x + 1].size()){
        auto it = mp[x + 1].lower_bound(y);
        if(it != mp[x + 1].end()){
            if(!comp[{x + 1, *it}]) dfs(x + 1, *it);
        }
    }
    auto it = mp[x].lower_bound(y);
    if(it != mp[x].begin()){
        it--;
        if(!comp[{x, *it}]) dfs(x, *it);
    }
    it = mp[x].upper_bound(y);
    if(it != mp[x].end()){
        if(!comp[{x, *it}]) dfs(x, *it);
    }
}
string check(int a, int b, int c, int d){
    if(!mp[a].size() || !mp[c].size() || c < a || d < b){
        return "NO\n";
    }
    auto it = mp[a].lower_bound(b);
    if(it != mp[a].end()){
        b = *it;
    }
    else{
        return "NO\n";
    }
    it = mp[c].upper_bound(d);
    if(it != mp[c].begin()){
        it--;
        d = *it;
    }
    else{
        return "NO\n";
    }
    if(c < a || d < b){
        return "NO\n";
    }
    if(comp[{a, b}] == comp[{c, d}]){
        return "YES\n";
    }
    else{
        return "NO\n";
    }
}
void solve(){
    int r, c, n, t;
    cin>>r>>c>>n;
    for(int i = 1; i <= n; i++){
        cin>>x[i]>>y[i]; 
        mp[x[i]].ins(y[i]);
    }
    cin>>t;
    for(int i = 1; i <= n; i++){
        if(!comp[{x[i], y[i]}]){
            timer++;
            dfs(x[i], y[i]);
        }
    }
    while(t--){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        if(a == c && b <= d){
            cout<<"YES\n";
        }
        else if(check(a, b, c, d) == "YES\n"){
            cout<<"YES\n";
        }
        else if(check(a, b, c - 1, d) == "YES\n"){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
}
signed main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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