| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 685918 | 2023-01-25T04:09:56 Z | Alihan_8 | Trampoline (info1cup20_trampoline) | C++17 | 774 ms | 78352 KB |
#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
const int N = 2e5+1;
int lift[20][N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int r, c, n; cin >> r >> c >> n;
map <int,set<pair<int,int>>> st;
vector <pair<int,int>> p(n);
for ( int i = 0; i < n; i++ ){
int x, y; cin >> x >> y;
st[--x].insert({--y, i+1});
p[i] = {x, y};
}
for ( int i = 0; i < n; i++ ){
auto [x, y] = p[i];
if ( !st.count(x+1) ) continue;
auto it = st[x+1].lower_bound({y, 0});
if ( it == st[x+1].end() ) continue;
lift[0][i+1] = it->second;
}
for ( int i = 1; i < 20; i++ ){
for ( int j = 1; j <= n; j++ ){
lift[i][j] = lift[i-1][lift[i-1][j]];
}
}
auto get = [&](int x, int k){
for ( int i = 19; i >= 0; i-- ){
if ( k >> i & 1 ) x = lift[i][x];
}
return x;
};
int t; cin >> t;
while ( t-- ){
int xs, ys, xe, ye;
cin >> xs >> ys >> xe >> ye;
if ( xs > xe or ys > ye or xe-xs > n ){
cout << "No\n";
continue;
}
if ( xs == xe ){
cout << "Yes\n";
continue;
}
xs--, xe--, ys--, ye--;
if ( !st.count(xs) ){
cout << "No\n";
continue;
}
auto it = st[xs].lower_bound({ys, 0});
if ( it == st[xs].end() ){
cout << "No\n";
continue;
}
int k = it->second, par = xe-xs-1;
k = get(k, par);
if ( !k or p[k-1].second > ye ) cout << "No\n";
else cout << "Yes\n";
}
cout << '\n';
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 2516 KB | 200 token(s): yes count is 21, no count is 179 |
| 2 | Correct | 7 ms | 2772 KB | 200 token(s): yes count is 70, no count is 130 |
| 3 | Correct | 5 ms | 2132 KB | 197 token(s): yes count is 25, no count is 172 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 288 ms | 47572 KB | 4000 token(s): yes count is 99, no count is 3901 |
| 2 | Correct | 257 ms | 47480 KB | 4000 token(s): yes count is 91, no count is 3909 |
| 3 | Correct | 231 ms | 47340 KB | 4000 token(s): yes count is 4000, no count is 0 |
| 4 | Correct | 263 ms | 47452 KB | 4000 token(s): yes count is 1991, no count is 2009 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 391 ms | 47980 KB | 200000 token(s): yes count is 110486, no count is 89514 |
| 2 | Correct | 418 ms | 48040 KB | 200000 token(s): yes count is 114664, no count is 85336 |
| 3 | Correct | 468 ms | 47892 KB | 200000 token(s): yes count is 86232, no count is 113768 |
| 4 | Correct | 452 ms | 48176 KB | 200000 token(s): yes count is 94603, no count is 105397 |
| 5 | Correct | 495 ms | 48120 KB | 200000 token(s): yes count is 94148, no count is 105852 |
| 6 | Correct | 550 ms | 54348 KB | 200000 token(s): yes count is 97163, no count is 102837 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 1620 KB | 5000 token(s): yes count is 3238, no count is 1762 |
| 2 | Correct | 7 ms | 1620 KB | 5000 token(s): yes count is 3837, no count is 1163 |
| 3 | Correct | 8 ms | 2072 KB | 5000 token(s): yes count is 4104, no count is 896 |
| 4 | Correct | 5 ms | 1620 KB | 5000 token(s): yes count is 3934, no count is 1066 |
| 5 | Correct | 8 ms | 1736 KB | 5000 token(s): yes count is 3384, no count is 1616 |
| 6 | Correct | 6 ms | 1620 KB | 5000 token(s): yes count is 3390, no count is 1610 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 665 ms | 63108 KB | 200000 token(s): yes count is 171404, no count is 28596 |
| 2 | Correct | 635 ms | 61480 KB | 200000 token(s): yes count is 161254, no count is 38746 |
| 3 | Correct | 471 ms | 59760 KB | 200000 token(s): yes count is 117455, no count is 82545 |
| 4 | Correct | 755 ms | 78352 KB | 200000 token(s): yes count is 182118, no count is 17882 |
| 5 | Correct | 540 ms | 66380 KB | 200000 token(s): yes count is 167565, no count is 32435 |
| 6 | Correct | 491 ms | 59744 KB | 200000 token(s): yes count is 156797, no count is 43203 |
| 7 | Correct | 465 ms | 59756 KB | 200000 token(s): yes count is 156797, no count is 43203 |
| 8 | Correct | 481 ms | 59860 KB | 200000 token(s): yes count is 122100, no count is 77900 |
| 9 | Correct | 656 ms | 65856 KB | 200000 token(s): yes count is 139670, no count is 60330 |
| 10 | Correct | 720 ms | 65868 KB | 200000 token(s): yes count is 165806, no count is 34194 |
| 11 | Correct | 774 ms | 72096 KB | 200000 token(s): yes count is 175646, no count is 24354 |
| 12 | Correct | 420 ms | 59716 KB | 200000 token(s): yes count is 134695, no count is 65305 |
| 13 | Correct | 371 ms | 59764 KB | 200000 token(s): yes count is 126733, no count is 73267 |
| 14 | Correct | 598 ms | 59848 KB | 200000 token(s): yes count is 155290, no count is 44710 |
| 15 | Correct | 451 ms | 59660 KB | 200000 token(s): yes count is 129674, no count is 70326 |