Submission #744829

#	Time	Username	Problem	Language	Result	Execution time	Memory
744829		fanwen	Trampoline (info1cup20_trampoline)	C++17	100 / 100	722 ms	52296 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

const int MAXN = 2e5 + 5;

int N, R, C, T;
map <int, vector <pair <int, int>>> lines;
int nxt[MAXN][20];

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}

    bool operator < (const Point &a) {
        return (x < a.x) || (x == a.x && y < a.y);
    }
} points[MAXN];

string calc_queries (int x, int y, int u, int v) {
    if(x == u) return (y <= v ? "Yes" : "No");
    if(lines.count(x)) {
        int id = lower_bound(ALL(lines[x]), make_pair(y, 0)) - lines[x].begin();
        if(id == lines[x].size()) return "No";
        id = lines[x][id].second;
        int jump = u - x - 1;
        REP(i, 32) if(BIT(jump, i)) {
            id = nxt[id][i];
            if(id == -1) return "No";
        }
        return (points[id].y <= v ? "Yes" : "No");
    }
    return "No";
}

void process(void) {
    cin >> R >> C >> N;
    FOR(i, 1, N) cin >> points[i].x >> points[i].y;
    sort(points + 1, points + N + 1);

    memset(nxt, -1, sizeof nxt);

    FOR(i, 1, N) lines[points[i].x].push_back(make_pair(points[i].y, i));
    FOR(i, 1, N) {
        if(lines.count(points[i].x + 1)) {
            int id = lower_bound(ALL(lines[points[i].x + 1]), make_pair(points[i].y, 0)) - lines[points[i].x + 1].begin();
            if(id < (int) lines[points[i].x + 1].size()) nxt[i][0] = lines[points[i].x + 1][id].second;
        }
    }
    for (int x = 1; MASK(x) <= N; ++x) FOR(i, 1, N) {
        if(nxt[i][x - 1] != -1) nxt[i][x] = nxt[nxt[i][x - 1]][x - 1];
    }
    // for (int x = 0; MASK(x) <= N; ++x) FOR(i, 1, N) {
    //     cout << nxt[i][x] << " \n"[i == N];
    // }
    cin >> T;
    while(T--) {
        int x, y, u, v; cin >> x >> y >> u >> v;
        cout << calc_queries(x, y, u, v) << " \n";
    }
}

signed main() {

    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = steady_clock::now();
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; ++i) {
        process();
        // cout << '\n';
    }

    auto end_time = steady_clock::now();

    cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

Compilation message (stderr)

trampoline.cpp: In function 'std::string calc_queries(int, int, int, int)':
trampoline.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if(id == lines[x].size()) return "No";
      |            ~~~^~~~~~~~~~~~~~~~~~
trampoline.cpp: In function 'int main()':
trampoline.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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