oj.uz

Submission #855531

# Submission time Handle Problem Language Result Execution time Memory
855531 2023-10-01T11:47:22 Z hariaakas646 Event Hopping (BOI22_events) C++17
30 / 100
 256 ms 19404 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

int n, q1;
vector<pair<pii, int>> dur, dur1;

vvi lift;

int binlift(int x, int c) {
    frange(i, 20) {
        if(c & (1<<i)) {
            x = lift[i][x];
        }
    }
    return x;
}

int main() {
    // usaco();
    scd(n);
    scd(q1);
    dur = vector<pair<pii, int>>(n);
    map<int, int> mv;
    frange(i, n) {
        scd(dur[i].f.s);
        scd(dur[i].f.f);
        dur[i].s = i+1;
        if(mv.find(dur[i].f.f) == mv.end()) {
            mv[dur[i].f.f] = dur[i].f.s;
        }
        else {
            mv[dur[i].f.f] = min(mv[dur[i].f.f], dur[i].f.s);
        }
    }

    dur1 = vector<pair<pii, int>>(n+1);
    forr(i, 1, n+1) {
        dur1[i] = dur[i-1];
    }
    sort(all(dur), greater<>());

    lift = vvi(20, vi(n+1));

    deque<pii> q;

    for(auto p : dur) {
        while(q.size() && q.front().f > p.f.f) {
            q.pop_front();
        }
        if(q.size()) {
            lift[0][p.s] = q.front().s;
        }
        else lift[0][p.s] = p.s;
        if(!q.size()) q.push_back(mp(p.f.s, p.s));
        else if(p.f.s < q.back().f) q.push_back(mp(p.f.s, p.s));
    }

    forr(i, 1, 20) {
        forr(j, 1, n+1) {
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }

    frange(_, q1) {
        int u, v;
        scd(u);
        scd(v);

        if(dur1[u].f.f > dur1[v].f.f) {
            printf("impossible\n");
            continue;
        }
        else if(u == v) {printf("0\n"); continue;}

        int lo = 0;
        int hi = n;

        while(lo != hi) {
            int mid = (lo + hi+1)/2;
            int x = binlift(u, mid);
            if(dur1[x].f.f >= dur1[v].f.f) {
                hi = mid-1;
            }
            else {
                lo = mid;
            }
        }
        int x = binlift(u, lo);
        if(dur1[v].f.s <= dur1[x].f.f) {
            printf("%d\n", lo+1);
        }
        else if(mv[dur1[v].f.f] <= dur1[x].f.f) {
            printf("%d\n", lo+2);
        }
        else {
            printf("impossible\n");
        }

    }


}

Compilation message

events.cpp: In function 'void usaco()':
events.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp: In function 'int main()':
events.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
events.cpp:50:5: note: in expansion of macro 'scd'
   50 |     scd(n);
      |     ^~~
events.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
events.cpp:51:5: note: in expansion of macro 'scd'
   51 |     scd(q1);
      |     ^~~
events.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
events.cpp:55:9: note: in expansion of macro 'scd'
   55 |         scd(dur[i].f.s);
      |         ^~~
events.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
events.cpp:56:9: note: in expansion of macro 'scd'
   56 |         scd(dur[i].f.f);
      |         ^~~
events.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
events.cpp:96:9: note: in expansion of macro 'scd'
   96 |         scd(u);
      |         ^~~
events.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
events.cpp:97:9: note: in expansion of macro 'scd'
   97 |         scd(v);
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 135 ms 18728 KB Output is correct
3 Correct 189 ms 18640 KB Output is correct
4 Correct 216 ms 18776 KB Output is correct
5 Correct 195 ms 18672 KB Output is correct
6 Correct 186 ms 18864 KB Output is correct
7 Correct 196 ms 18892 KB Output is correct
8 Correct 130 ms 19276 KB Output is correct
9 Correct 155 ms 19404 KB Output is correct
10 Correct 256 ms 19292 KB Output is correct
11 Correct 190 ms 19400 KB Output is correct
12 Correct 106 ms 16180 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 15800 KB Output is correct
2 Correct 194 ms 15816 KB Output is correct
3 Correct 217 ms 15776 KB Output is correct
4 Correct 172 ms 16292 KB Output is correct
5 Correct 202 ms 19216 KB Output is correct
6 Correct 150 ms 18892 KB Output is correct
7 Correct 144 ms 18636 KB Output is correct
8 Correct 153 ms 19020 KB Output is correct
9 Correct 81 ms 17724 KB Output is correct
10 Correct 166 ms 18740 KB Output is correct
11 Correct 135 ms 18380 KB Output is correct
12 Correct 193 ms 18400 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 135 ms 18728 KB Output is correct
3 Correct 189 ms 18640 KB Output is correct
4 Correct 216 ms 18776 KB Output is correct
5 Correct 195 ms 18672 KB Output is correct
6 Correct 186 ms 18864 KB Output is correct
7 Correct 196 ms 18892 KB Output is correct
8 Correct 130 ms 19276 KB Output is correct
9 Correct 155 ms 19404 KB Output is correct
10 Correct 256 ms 19292 KB Output is correct
11 Correct 190 ms 19400 KB Output is correct
12 Correct 106 ms 16180 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -