Submission #306186

#	Time	Username	Problem	Language	Result	Execution time	Memory
306186		Matteo_Verz	Trampoline (info1cup20_trampoline)	C++11	100 / 100	1980 ms	57372 KiB

trampoline

// nu ar fi stricat niste teste :)
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
 
using namespace std;
 
const int LOG = 18;
const int N = 2e5;
 
int dp[5 + LOG][5 + N];
set <pair<int,int>> s[5 + N];
map <int, int> norm;
 
struct ura{
    int x, y, cheie;
 
    bool operator < (const ura a) const{
        if(a.x == x) return y < a.y;
        return x < a.x;
    }
}v[5 + N];
 
int r, c, n, t;
 
 
int find_parent(int pos){
    set <pair<int,int>> :: iterator it;
 
    it = s[norm[v[pos].x + 1]].upper_bound(make_pair(v[pos].y, 0));
    return (*it).second;
}
 
void solve(int xi, int yi, int xf, int yf){
    int r, pas;
    r = 0;
    pas = 1 << LOG;
 
    while(pas){
        if(r + pas <= n && (v[r + pas].x < xi || (v[r + pas].x == xi && v[r + pas].y < yi)))
            r += pas;
        pas >>= 1;
    }
 
    r++;
    if(v[r].x != xi || (v[r].x == xi && v[r].y < yi)){
        cout << "No\n";
        return;
    }
    int stramos = xf - xi - 1;
 
    for(int i = LOG; 0 <= i; i--)
        if(stramos & (1 << i))
            r = dp[i][r];
 
    if(r > 0){
        if((v[r].x == xf - 1 || v[r].x == xf) && v[r].y <= yf) cout << "Yes\n";
        else cout << "No\n";
    } else cout << "No\n";
}
 
int main() {
    int cur(0);
    cin >> r >> c >> n;
 
    for(int i = 1; i <= n; i++){
        cin >> v[i].x >> v[i].y;
        if(norm[v[i].x] == 0)
            norm[v[i].x] = ++cur;
        if(!v[i].cheie)
            v[i].cheie = norm[v[i].x];
    }
 
    sort(v + 1, v + n + 1);
 
    for(int i = 1; i <= n; i++)
        s[v[i].cheie].insert(make_pair(v[i].y, i));
 
    for(int i = 1; i <= n; i++){
        int pr = find_parent(i);
 
        if(v[pr].x == v[i].x + 1 && v[pr].y >= v[i].y) // daca e in dreapta lui
            dp[0][i] = pr;
    }
 
    for(int i = 1; i < LOG; i++)
        for(int j = 1; j <= n; j++)
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
 
    cin >> t;
    while(t--){
        int xi, yi, xf, yf;
        cin >> xi >> yi >> xf >> yf;
 
        if(xf < xi || (xf == xi && yf < yi)) cout << "No\n";
        else if(xf == xi && yi <= yf) cout << "Yes\n";
 
        else solve(xi, yi, xf, yf);
    }
    return 0;
}

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