oj.uz

Submission #970608

# Submission time Handle Problem Language Result Execution time Memory
970608 2024-04-26T19:16:46 Z hariaakas646 Railway Trip 2 (JOI22_ho_t4) C++14
25 / 100
 1971 ms 71696 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);
}

template <class T>
struct MinSegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        return min(x, y); // Any required operation
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void update(int x, int l, int r, int id, T val)
    {
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
        return query(0, 0, size - 1, lx, rx);
    }
};

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        return max(x, y); // Any required operation
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void update(int x, int l, int r, int id, T val)
    {
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
        return query(0, 0, size - 1, lx, rx);
    }
};

vector<SegTree<int>> lift1(20);
vector<MinSegTree<int>> lift2(20);

int binlift(int st, int en) {
    int tot = 0;
    pii curr = mp(st, st);
    for(int i=19; i>=0; i--) {
        pii tmp = mp(lift2[i].query(curr.f, curr.s), lift1[i].query(curr.f, curr.s));
        
        if(!(tmp.f <= en && en <= tmp.s)) {
            curr = tmp;
            tot += (1<<i);
        }
    }
    curr = mp(lift2[0].query(curr.f, curr.s), lift1[0].query(curr.f, curr.s));
    // printf("%d %d\n", curr.f, curr.s);
    if(curr.f <= en && en <= curr.s)
        return tot + 1;
    else return -1;
}

int main() {
    // usaco();
    int n, k;
    scd(n);
    scd(k);
    int m;
    scd(m);

    vii vec(m);

    frange(i, m) {
        scd(vec[i].s);
        scd(vec[i].f);
    }

    sort(all(vec));
    seti act;
    frange(i, n) act.insert(i+1);

    sort(all(vec), greater<>());
    lift1[0].init(n+1, 0);
    forr(i, 1, n+1) {
        lift1[0].set(i, i);
    }
    for(auto p : vec) {
        if(p.f > p.s) {
            auto it = act.lower_bound(p.s);
            while(it != act.end() && *it < max(p.s+k, p.f)) {
                lift1[0].set(*it, p.f);
                act.erase(it);
                it=act.lower_bound(p.s);
            }
        }
    }
    lift1[0].build();
    frange(i, n) act.insert(i+1);

    sort(all(vec));
    lift2[0].init(n+1, 1e9);
    forr(i, 1, n+1) {
        lift2[0].set(i, i);
    }
    for(auto p : vec) {
        if(p.f < p.s) {
            auto it = act.lower_bound(max(p.f+1, p.s-k+1));
            while(it != act.end() && *it <= p.s) {
                lift2[0].set(*it, p.f);
                act.erase(it);
                it=act.lower_bound(max(p.f+1, p.s-k+1));
            }
        }
    }
    lift2[0].build();

    forr(i, 1, 20) {
        lift1[i].init(n+1, 0);
        lift2[i].init(n+1, 1e9);
        forr(j, 1, n+1) {
            lift1[i].set(j, lift1[i-1].query(lift2[i-1].query(j, j), lift1[i-1].query(j, j)));
            lift2[i].set(j, lift2[i-1].query(lift2[i-1].query(j, j), lift1[i-1].query(j, j)));
        }
        lift1[i].build();
        lift2[i].build();
    }

    int q;
    scd(q);

    frange(_, q) {
        int st, en;
        scd(st);
        scd(en);
        printf("%d\n", binlift(st, en));
    }
}

Compilation message

Main.cpp: In function 'void usaco()':
Main.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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:258:5: note: in expansion of macro 'scd'
  258 |     scd(n);
      |     ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:259:5: note: in expansion of macro 'scd'
  259 |     scd(k);
      |     ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:261:5: note: in expansion of macro 'scd'
  261 |     scd(m);
      |     ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:266:9: note: in expansion of macro 'scd'
  266 |         scd(vec[i].s);
      |         ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:267:9: note: in expansion of macro 'scd'
  267 |         scd(vec[i].f);
      |         ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:321:5: note: in expansion of macro 'scd'
  321 |     scd(q);
      |     ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:325:9: note: in expansion of macro 'scd'
  325 |         scd(st);
      |         ^~~
Main.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)
      |                ~~~~~^~~~~~~~~~
Main.cpp:326:9: note: in expansion of macro 'scd'
  326 |         scd(en);
      |         ^~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 11.0

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

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1651 ms 66548 KB Output is correct
2 Correct 1602 ms 67968 KB Output is correct
3 Correct 1590 ms 65064 KB Output is correct
4 Correct 1529 ms 66532 KB Output is correct
5 Correct 1499 ms 66688 KB Output is correct
6 Correct 1484 ms 67020 KB Output is correct
7 Correct 1535 ms 70336 KB Output is correct
8 Correct 1690 ms 66920 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1826 ms 71696 KB Output is correct
2 Correct 1898 ms 69712 KB Output is correct
3 Correct 1971 ms 68776 KB Output is correct
4 Correct 1772 ms 68004 KB Output is correct
5 Incorrect 1761 ms 67800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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