oj.uz

Submission #306186

# Submission time Handle Problem Language Result Execution time Memory
306186 2020-09-24T19:44:46 Z Matteo_Verz Trampoline (info1cup20_trampoline) C++11
100 / 100
 1980 ms 57372 KB 
// 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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 11008 KB 200 token(s): yes count is 21, no count is 179
2 Correct 19 ms 11136 KB 200 token(s): yes count is 70, no count is 130
3 Correct 16 ms 10752 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 37520 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 316 ms 37624 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 281 ms 37112 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 317 ms 37496 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1644 ms 48100 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 1660 ms 48092 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 1640 ms 47996 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 1666 ms 48180 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 1653 ms 48120 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 1725 ms 51092 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10752 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 47 ms 10752 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 49 ms 11384 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 46 ms 10752 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 47 ms 10872 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 46 ms 10752 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1858 ms 51752 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 1783 ms 49144 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 1681 ms 47992 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 1980 ms 57372 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 1745 ms 51468 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 1678 ms 48120 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 1675 ms 48120 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 1679 ms 48140 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 1832 ms 51100 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 1839 ms 51448 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 1916 ms 54184 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 1663 ms 48012 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 1665 ms 48120 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 1904 ms 48248 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 1665 ms 47988 KB 200000 token(s): yes count is 129674, no count is 70326