oj.uz

Submission #526870

# Submission time Handle Problem Language Result Execution time Memory
526870 2022-02-16T13:03:29 Z abc864197532 Railway Trip 2 (JOI22_ho_t4) C++17
27 / 100
 2000 ms 226100 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); 
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 1e5 + 7, logN = 18, K = 111, M = N * 20;

pii mer(pii a, pii b) {
    return mp(min(a.X, b.X), max(a.Y, b.Y));
}

struct Seg {
    int l, r, m, mn, mx, lzmn, lzmx;
    Seg* ch[2];
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lzmn(-1), lzmx(-1) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
            pull();
        } else {
            mn = l, mx = l + 1;
        }
    }
    void pull() {
        mn = min(ch[0]->mn, ch[1]->mn);
        mx = max(ch[0]->mx, ch[1]->mx);
    }
    void give_mn(int v) {
        if (lzmn != -1 && lzmn <= v)
            return;
        mn = min(mn, v), lzmn = v;
    }
    void give_mx(int v) {
        if (lzmx != -1 && lzmx >= v)
            return;
        mx = max(mx, v), lzmx = v;
    }
    void push() {
        if (lzmn != -1)
            ch[0]->give_mn(lzmn), ch[1]->give_mn(lzmn);
        if (lzmx != -1)
            ch[0]->give_mx(lzmx), ch[1]->give_mx(lzmx);
        lzmn = lzmx = -1;
    }
    void modify_mn(int a, int b, int v) {
        if (a <= l && r <= b)
            give_mn(v);
        else {
            push();
            if (a < m)
                ch[0]->modify_mn(a, b, v);
            if (m < b)
                ch[1]->modify_mn(a, b, v);
            pull();
        }
    }
    void modify_mx(int a, int b, int v) {
        if (a <= l && r <= b)
            give_mx(v);
        else {
            push();
            if (a < m)
                ch[0]->modify_mx(a, b, v);
            if (m < b)
                ch[1]->modify_mx(a, b, v);
            pull();
        }
    }
    pii query(int a, int b) {
        if (a <= l && r <= b)
            return mp(mn, mx);
        pii ans = mp(1 << 30, -1 << 30);
        push();
        if (a < m)
            ans = mer(ans, ch[0]->query(a, b));
        if (m < b)
            ans = mer(ans, ch[1]->query(a, b));
        return ans;
    }
};

Seg* root[logN];

int main () {
    owo;
    int n, k, m, q;
    cin >> n >> k >> m;
    root[0] = new Seg(0, n);
    for (int i = 0, l, r; i < m; ++i) {
        cin >> l >> r;
        if (l < r)
            --l, root[0]->modify_mx(l, min(l + k, r), r);
        else
            --r, root[0]->modify_mn(max(l - k, r), l, r);
    }
    for (int j = 1; j < logN; ++j) {
        root[j] = new Seg(0, n);
        for (int i = 0; i < n; ++i) {
            int l, r; tie(l, r) = root[j - 1]->query(i, i + 1);
            tie(l, r) = root[j - 1]->query(l, r);
            root[j]->modify_mn(i, i + 1, l);
            root[j]->modify_mx(i, i + 1, r);
        }
    }
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r, --l, --r;
        {
            int curl, curr;
            tie(curl, curr) = root[logN - 1]->query(l, l + 1);
            if (r < curl || curr <= r) {
                cout << -1 << endl;
                continue;
            }
        }
        int curl = l, curr = l + 1, ans = 0;
        for (int i = logN - 1; ~i; --i) {
            int nxtl, nxtr; tie(nxtl, nxtr) = root[i]->query(curl, curr);
            if (r < nxtl || nxtr <= r) {
                ans |= 1 << i;
                tie(curl, curr) = mp(nxtl, nxtr);
            }
        }
        cout << ans + 1 << endl;
    }
}

Compilation message

Main.cpp: In constructor 'Seg::Seg(int, int)':
Main.cpp:55:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lzmn(-1), lzmx(-1) {
      |                                            ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 4 ms 972 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 3 ms 972 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 4 ms 972 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 3 ms 972 KB Output is correct
13 Correct 27 ms 4820 KB Output is correct
14 Correct 24 ms 4764 KB Output is correct
15 Correct 16 ms 4736 KB Output is correct
16 Correct 26 ms 4712 KB Output is correct
17 Correct 25 ms 4824 KB Output is correct
18 Correct 23 ms 4812 KB Output is correct
19 Correct 24 ms 4556 KB Output is correct
20 Correct 19 ms 4756 KB Output is correct
21 Correct 14 ms 4704 KB Output is correct
22 Correct 23 ms 4732 KB Output is correct
23 Correct 23 ms 4760 KB Output is correct
24 Correct 22 ms 4744 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 225604 KB Output is correct
2 Correct 1281 ms 225760 KB Output is correct
3 Correct 1296 ms 225644 KB Output is correct
4 Correct 1161 ms 225624 KB Output is correct
5 Correct 1169 ms 225644 KB Output is correct
6 Correct 1256 ms 225732 KB Output is correct
7 Correct 945 ms 225652 KB Output is correct
8 Correct 962 ms 223412 KB Output is correct
9 Correct 1091 ms 225612 KB Output is correct
10 Correct 1361 ms 225736 KB Output is correct
11 Correct 1195 ms 225776 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 226000 KB Output is correct
2 Correct 1531 ms 225908 KB Output is correct
3 Execution timed out 2012 ms 226100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1342 ms 225860 KB Output is correct
2 Execution timed out 2093 ms 226016 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 4 ms 972 KB Output is correct
3 Correct 4 ms 972 KB Output is correct
4 Correct 3 ms 972 KB Output is correct
5 Correct 3 ms 972 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 3 ms 844 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 3 ms 972 KB Output is correct
13 Correct 27 ms 4820 KB Output is correct
14 Correct 24 ms 4764 KB Output is correct
15 Correct 16 ms 4736 KB Output is correct
16 Correct 26 ms 4712 KB Output is correct
17 Correct 25 ms 4824 KB Output is correct
18 Correct 23 ms 4812 KB Output is correct
19 Correct 24 ms 4556 KB Output is correct
20 Correct 19 ms 4756 KB Output is correct
21 Correct 14 ms 4704 KB Output is correct
22 Correct 23 ms 4732 KB Output is correct
23 Correct 23 ms 4760 KB Output is correct
24 Correct 22 ms 4744 KB Output is correct
25 Correct 1235 ms 225604 KB Output is correct
26 Correct 1281 ms 225760 KB Output is correct
27 Correct 1296 ms 225644 KB Output is correct
28 Correct 1161 ms 225624 KB Output is correct
29 Correct 1169 ms 225644 KB Output is correct
30 Correct 1256 ms 225732 KB Output is correct
31 Correct 945 ms 225652 KB Output is correct
32 Correct 962 ms 223412 KB Output is correct
33 Correct 1091 ms 225612 KB Output is correct
34 Correct 1361 ms 225736 KB Output is correct
35 Correct 1195 ms 225776 KB Output is correct
36 Correct 1788 ms 226000 KB Output is correct
37 Correct 1531 ms 225908 KB Output is correct
38 Execution timed out 2012 ms 226100 KB Time limit exceeded
39 Halted 0 ms 0 KB -