oj.uz

답안 #685918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685918 2023-01-25T04:09:56 Z Alihan_8 Trampoline (info1cup20_trampoline) C++17
100 / 100
 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

trampoline.cpp: In function 'void IO(std::string)':
trampoline.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 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

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 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