oj.uz

Submission #744829

# Submission time Handle Problem Language Result Execution time Memory
744829 2023-05-19T06:35:18 Z fanwen Trampoline (info1cup20_trampoline) C++17
100 / 100
 722 ms 52296 KB 
#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

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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17620 KB 200 token(s): yes count is 21, no count is 179
2 Correct 11 ms 17656 KB 200 token(s): yes count is 70, no count is 130
3 Correct 10 ms 17648 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 22092 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 114 ms 22080 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 104 ms 21132 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 108 ms 22028 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 32228 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 240 ms 32072 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 250 ms 31944 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 306 ms 32460 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 307 ms 32436 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 441 ms 38208 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17876 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 13 ms 17876 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 14 ms 18420 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 14 ms 17832 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 15 ms 18024 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 15 ms 17936 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 39736 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 476 ms 34184 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 284 ms 31944 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 722 ms 52296 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 456 ms 39012 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 274 ms 32328 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 279 ms 32324 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 278 ms 31824 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 565 ms 38352 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 578 ms 38356 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 666 ms 44748 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 239 ms 32024 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 262 ms 32348 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 374 ms 32544 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 248 ms 32300 KB 200000 token(s): yes count is 129674, no count is 70326