Submission #1208687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208687		horiaboeriu	Trampoline (info1cup20_trampoline)	C++20	100 / 100	104 ms	21532 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
#define MAX 200000
#define MAXL 18
int rez[MAX], rmq[MAXL][MAX + 1];
struct nume {
    int lin, col;
} v[MAX + 1];
struct nume2 {
    int x1, y1, x2, y2, poz;
} v2[MAX];
char cmp(nume a, nume b) {
    if (a.lin == b.lin) {
        return a.col < b.col;
    }
    return a.lin < b.lin;
}
char cmp2(nume2 a, nume2 b) {
    if (a.x1 == b.x1) {
        return a.y1 < b.y1;
    }
    return a.x1 < b.x1;
}
int readInt() {
    int x;
    char ch;
    ch = fgetc(stdin);
    while (isspace(ch)) {
        ch = fgetc(stdin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(stdin);
    }
    return x;
}
void calcRmq(int n) {
    int i, j, p;
    j = 1;
    for (i = 1; i <= n; i++) {
        while (j <= n && v[j].lin <= v[i].lin) {
            j++;
        }
        while (j <= n && v[j].lin == v[i].lin + 1 && v[j].col < v[i].col) {
            j++;
        }
        if (j <= n && v[j].lin == v[i].lin + 1) {//daca j = n + 1, ramane 0 ca santinela
            rmq[0][i] = j;
        }
    }

    p = j = 1;
    while (p <= n) {
        for (i = 1; i <= n; i++) {
            rmq[j][i] = rmq[j - 1][rmq[j - 1][i]];
        }
        p *= 2;
        j++;
    }
}
int main()
{
    int n, t, nrlin, nrcol, i, j, p2, p, k, poz;
    scanf("%d%d%d", &nrlin, &nrcol, &n);
    //trebuie ca in fiecare dreptunghi sa apara cate o trambulina verde pe fiecare linie si sa fie si pe coloane in ordine crescatoare
    //binary lifting si o sa vad prima trambaulina si care e a k-a urmatoare
    //ca sa il gasesec pe primul de pe acea linie sortez queryurile
    for (i = 1; i <= n; i++) {
        v[i].lin = readInt();
        v[i].col = readInt();
    }
    sort(v + 1, v + n + 1, cmp);
    t = readInt();
    for (i = 0; i < t; i++) {
        v2[i].x1 = readInt();
        v2[i].y1 = readInt();
        v2[i].x2 = readInt();
        v2[i].y2 = readInt();
        v2[i].poz = i;
    }
    sort(v2, v2 + t, cmp2);
    calcRmq(n);
    j = 1;
    p2 = 0;
    while ((1 << p2) <= n) {
        p2++;
    }
    p2--;
    for (i = 0; i < t; i++) {
        while (j <= n && v[j].lin < v2[i].x1) {
            j++;
        }
        while (j <= n && v[j].lin == v2[i].x1 && v[j].col < v2[i].y1) {
            j++;
        }
        if (v2[i].x2 < v2[i].x1 || v2[i].y2 < v2[i].y1) {
            rez[v2[i].poz] = 0;
        } else if (v2[i].x1 == v2[i].x2) {
            rez[v2[i].poz] = 1;
        } else if (j > n || v[j].lin > v2[i].x1 || v[j].col > v2[i].y2) {
            rez[v2[i].poz] = 0;
        } else {
            k = v2[i].x2 - v2[i].x1 - 1;
            poz = j;
            for (p = p2; p >= 0; p--) {
                if ((1 << p) <= k) {
                    poz = rmq[p][poz];
                    k -= (1 << p);
                }
            }
            if (k > 0 || poz == 0 || v[poz].lin > v2[i].x2 || v[poz].col > v2[i].y2) {
                rez[v2[i].poz] = 0;
            } else {
                rez[v2[i].poz] = 1;
            }
        }
    }
    for (i = 0; i < t; i++) {
        if (rez[i] == 0) {
            printf("No\n");
        } else {
            printf("Yes\n");
        }
    }
    return 0;
}

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d%d", &nrlin, &nrcol, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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