oj.uz

Submission #685535

# Submission time Handle Problem Language Result Execution time Memory
685535 2023-01-24T13:34:52 Z Farhan_HY Trampoline (info1cup20_trampoline) C++14
0 / 100
 489 ms 78100 KB 
#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 1e5 + 5;
const int M = 1e3 + 3;
const int inf = 1e18;
const int mod = 1e9 + 7;
int r, c, n, q, sp[30][N];
pair<int, int> a[N];
map<int, set<int>> tramps;
map<pair<int, int>, int> trampNum;

void build() {
    for(int i = 1; i <= n; i++) {
        auto it = tramps[a[i].S + 1].lower_bound(a[i].F);
        if (it != tramps[a[i].S + 1].end())
            sp[0][i] = trampNum[{*it, a[i].S + 1}];
    }
    for(int j = 1; j < 26; j++)
        for(int i = 1; i <= n; i++)
            sp[j][i] = sp[j - 1][sp[j - 1][i]];
}

int get(int i, int num) {
    int me = i;
    for(int j = 0; j < 26; j++) {
        if ((num & (1 << j)) == 0) continue;
        int he = sp[j][me];
        if (he == 0) return 0;
        me = he;
    }
    return me;
}

main() {
    IOS
    cin >> r >> c >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].S >> a[i].F;
        tramps[a[i].S].insert(a[i].F);
        trampNum[a[i]] = i;
    }
    build();
    cin >> q;
    while(q--) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        if (x1 > x2) {
            cout << "No\n";
            continue;
        }
        if (y1 == y2) {
            cout << "Yes\n";
            continue;
        }
        auto it = tramps[y1].lower_bound(x1);
        if (it == tramps[y1].end()) {
            cout << "No\n";
            continue;
        }
        x1 = *it;
        int num = trampNum[{y1, x1}];
        int he = get(num, y2 - y1);
        if (he != 0 && a[he].F <= x2) {
            cout << "Yes\n";
            continue;
        }
        he = get(num, y2 - y1 - 1);
        if (he != 0 && a[he].F <= x2) {
            cout << "Yes\n";
            continue;
        }
        cout << "No\n";
    }
}
/*
5 5 5
1 1
2 2
3 3
4 4
5 5
1
1 1 2 1
*/

Compilation message

trampoline.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3412 KB expected YES, found NO [5th token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 463 ms 50288 KB expected NO, found YES [1st token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 414 ms 54348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2388 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 489 ms 78100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -