oj.uz

Submission #855528

# Submission time Handle Problem Language Result Execution time Memory
855528 2023-10-01T11:46:11 Z hariaakas646 Event Hopping (BOI22_events) C++17
0 / 100
 246 ms 18636 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.s] <= 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 18636 KB Output is correct
2 Correct 246 ms 18620 KB Output is correct
3 Correct 197 ms 18508 KB Output is correct
4 Incorrect 159 ms 18632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -