Submission #685528

#	Time	Username	Problem	Language	Result	Execution time	Memory
685528		Farhan_HY	Trampoline (info1cup20_trampoline)	C++14	0 / 100	741 ms	77204 KiB

trampoline

#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].upper_bound(a[i].F);
        if (tramps[a[i].S - 1].size() && it != tramps[a[i].S - 1].begin())
            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;
        it = tramps[y2].upper_bound(x2);
        if (tramps[y2].size() && it != tramps[y2].begin()) {
            it--;
            int par = get(trampNum[{*it, y2}], y2 - y1);
            if (par == trampNum[{x1, y1}]) {
                cout << "Yes\n";
                continue;
            }
        }
        it = tramps[y2 - 1].upper_bound(x2);
        if (tramps[y2 - 1].size() && it != tramps[y2 - 1].begin()) {
            it--;
            int num = trampNum[{*it, y2 - 1}];
            int par = get(num, y2 - y1 - 1);
            if (par == trampNum[{x1, y1}]) {
                cout << "Yes\n";
                continue;
            }
        }
        cout << "No\n";
    }
}

Compilation message (stderr)

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

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