Submission #1145119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145119		saidpon	Trampoline (info1cup20_trampoline)	C++20	0 / 100	1212 ms	68760 KiB

trampoline

#include <bits/stdc++.h>
#define nemeshay ios_base::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
#define int long long
#define sigma signed
#define pb push_back
#define fr first
#define sc second
#define pii pair<int, int>
#define double long double
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define OK cout << "OK" << endl
#define Ok cout << "Ok" << endl
#define nosolve cout << "-1" << endl
using namespace std;
const int N = 2e6 + 2, inf = 1e18 + 7, mod = 998244353;
pii a[N];
int c[N], p[N];
vector <int> pon[N];
sigma main() {
    nemeshay
    int R, C, n;
    cin >> R >> C >> n;
    map <pii, int> ladno;
    for (int i = 0; i < n; i++) {
        cin >> a[i].fr >> a[i].sc;
        pon[a[i].fr].pb(a[i].sc);
    }
    for (int i = 0; i < N; i++) sort (pon[i].begin(), pon[i].end());
    sort (a, a + n);
    for (int i = n - 1; i > 0; i--) {
        ladno[{a[i].fr, a[i].sc}] = i;
        int l = 0, r = i - 1;
        while (r - l > 1) {
            int m = l + r >> 1;
            if (a[m].fr < a[i].fr) l = m;
            else r = m;
        }
        if (r > -1 && a[r].fr < a[i].fr) p[i] = r;
        else if (a[l].fr < a[i].fr) p[i] = l;
    }
    p[0] = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (c[i]) continue;
        int x = i;
        while (x > -1) c[x] = i, x = p[x];
    }
    int q;
    cin >> q;
    while (q--) {
        int xs, ys, xf, yf;
        cin >> xs >> ys >> xf >> yf;
        if (xs == xf) {
            YES;
            continue;
        }
        xf--;
        int ind1 = lower_bound(pon[xs].begin(), pon[xs].end(), ys) - pon[xs].begin();
        if (ind1 == pon[xs].size()) {
            NO;
            continue;
        }
        int ind2 = upper_bound(pon[xf].begin(), pon[xf].end(), yf) - pon[xf].begin();
        ind2--;
        if (ind2 == -1) {
            NO;
            continue;
        }
        if (c[ladno[{xs, pon[xs][ind1]}]] == c[ladno[{xf, pon[xf][ind2]}]] || xs == xf) YES;
        else NO;
    }
}

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