oj.uz

Submission #676839

# Submission time Handle Problem Language Result Execution time Memory
676839 2023-01-01T10:38:33 Z abysmal Railway Trip 2 (JOI22_ho_t4) C++14
27 / 100
 2000 ms 60488 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<string>

using namespace std;

const int64_t INF = (int64_t) 4 * 1e5 + 5;
const int64_t mINF = 18;
const int64_t MOD = (int64_t) 1e9 + 7;
const int nbit = 11;
const int ndig = 10;
const int nchar = 26;
const int p1 = 31;
const int p2 = 53;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};
// 0 right // 1 down // 2 left // 3 up

struct Solution
{
    int n;
    int k;
    int m;
    int sz;
    int LOG;
    vector<vector<int> > a;
    vector<vector<int> > b;
    vector<vector<int> > treer;
    vector<vector<int> > treel;
    vector<vector<pair<int, int> > > range;
    Solution() {}

    void solve()
    {
        cin >> n >> k >> m;

        a.resize(n);
        b.resize(n);
        for(int i = 0; i < m; i++)
        {
            int u;
            int v;
            cin >> u >> v;
            u--; v--;

            if(u < v) a[u].push_back(v);
            else b[u].push_back(v);
        }

        buildTree();

        int q;
        cin >> q;
        for(int i = 0; i < q; i++)
        {
            int s;
            int t;
            cin >> s >> t;
            s--; t--;

            int l = 1;
            int r = n;
            int ans = -1;
            while(l <= r)
            {
                int mid = l + (r - l) / 2;

                if(check(mid, s, t))
                {
                    ans = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }

            cout << ans << "\n";
        }
    }

    bool check(int dis, int& s, int& t)
    {
        int l = s;
        int r = s;

        while(dis != 0)
        {
            int bt = 31 - __builtin_clz(dis);

            int newl = get(1, 0, sz - 1, l, r, bt, 0);
            int newr = get(1, 0, sz - 1, l, r, bt, 1);

            l = newl;
            r = newr;
            dis ^= MASK(bt);
        }

        return (l <= t && t <= r);
    }

    void buildTree()
    {
        sz = n;
        LOG = 0;
        while(MASK(LOG) <= n) LOG++;
        while(__builtin_popcount(sz) != 1) sz++;
        treer.resize(LOG, vector<int>(sz * 2, -1));
        treel.resize(LOG, vector<int>(sz * 2, n));
        range.resize(LOG, vector<pair<int, int> >(n, make_pair(-1, -1)));
        for(int i = 0; i < n; i++)
        {
            range[0][i] = make_pair(i, i);
        }

        deque<pair<int, int> > dq;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < (int) a[i].size(); j++)
            {
                int v = a[i][j];

                while(!dq.empty() && dq.back().second <= v) dq.pop_back();
                dq.push_back(make_pair(i, v));
            }

            while(!dq.empty() && (dq.front().first + k - 1 < i || dq.front().second < i)) dq.pop_front();
            if(dq.empty()) continue;

            range[0][i].second = dq.front().second;
        }

        deque<pair<int, int> > dq2;
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = 0; j < (int) b[i].size(); j++)
            {
                int v = b[i][j];

                while(!dq2.empty() && dq2.back().second >= v) dq2.pop_back();
                dq2.push_back(make_pair(i, v));
            }

            while(!dq2.empty() && (dq2.front().first - k + 1 > i || dq2.front().second > i)) dq2.pop_front();
            if(dq2.empty()) continue;

            range[0][i].first = dq2.front().second;
        }

        for(int i = 0; i < n; i++)
        {
            treel[0][sz + i] = range[0][i].first;
            treer[0][sz + i] = range[0][i].second;
        }

        for(int i = sz - 1; i >= 1; i--)
        {
            treer[0][i] = max(treer[0][i * 2], treer[0][i * 2 + 1]);
            treel[0][i] = min(treel[0][i * 2], treel[0][i * 2 + 1]);
        }

        for(int i = 1; i < LOG; i++)
        {
//            cerr << "i = " << i << "\n";
            int prev = i - 1;
            for(int j = 0; j < n; j++)
            {
                int l = range[i - 1][j].first;
                int r = range[i - 1][j].second;
                int newl = get(1, 0, sz - 1, l, r, prev, 0);
                int newr = get(1, 0, sz - 1, l, r, prev, 1);
//                cerr << "l = " << l << " ; r = " << r << "\n";
//                cerr << "newl = " << newl << " ; newr = " << newr << "\n";
                update(j, i, newl, 0);
                update(j, i, newr, 1);

                range[i][j] = make_pair(newl, newr);
            }
//            cerr << "\n";
        }
    }

    void update(int& id, int& d, int& val, int t)
    {
        if(t == 0) treel[d][sz + id] = min(treel[d][sz + id], val);
        else treer[d][sz + id] = max(treer[d][sz + id], val);

        for(int i = (sz + id) / 2; i >= 1; i /= 2)
        {
            if(t == 0) treel[d][i] = min(treel[d][i * 2], treel[d][i * 2 + 1]);
            else treer[d][i] = max(treer[d][i * 2], treer[d][i * 2 + 1]);
        }
    }

    int get(int node, int nleft, int nright, int& left, int& right, int& d, int t)
    {
        if(left <= nleft && nright <= right)
        {
            if(t == 0) return treel[d][node];
            return treer[d][node];
        }

        if(nleft > right || nright < left)
        {
            if(t == 0) return n;
            return -1;
        }

        int mid = nleft + (nright - nleft) / 2;

        int t1 = get(node * 2, nleft, mid, left, right, d, t);
        int t2 = get(node * 2 + 1, mid + 1, nright, left, right, d, t);
        if(t == 0) return min(t1, t2);
        return max(t1, t2);
    }

    int modsub(int t1, int t2)
    {
        int res = t1 - t2;
        if(res < 0) res += MOD;

        return res;
    }

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;

        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return (res % MOD);
    }

    bool BIT(int& mask, int& j)
    {
        return (mask & MASK(j));
    }

    int64_t MASK(int64_t j)
    {
        return (1LL << j);
    }
};

void __startup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __startup();
    int t = 1;
//    cin >> t;

    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 2 ms 440 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 36 ms 980 KB Output is correct
14 Correct 32 ms 980 KB Output is correct
15 Correct 7 ms 996 KB Output is correct
16 Correct 27 ms 1000 KB Output is correct
17 Correct 33 ms 980 KB Output is correct
18 Correct 14 ms 1016 KB Output is correct
19 Correct 21 ms 992 KB Output is correct
20 Correct 12 ms 980 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 23 ms 980 KB Output is correct
23 Correct 20 ms 1004 KB Output is correct
24 Correct 28 ms 980 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 56844 KB Output is correct
2 Correct 775 ms 56716 KB Output is correct
3 Correct 840 ms 57308 KB Output is correct
4 Correct 746 ms 56548 KB Output is correct
5 Correct 569 ms 57800 KB Output is correct
6 Correct 751 ms 60448 KB Output is correct
7 Correct 424 ms 60488 KB Output is correct
8 Correct 471 ms 56420 KB Output is correct
9 Correct 419 ms 56568 KB Output is correct
10 Correct 729 ms 58296 KB Output is correct
11 Correct 659 ms 58288 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1912 ms 57136 KB Output is correct
2 Execution timed out 2086 ms 57928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 56880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 2 ms 440 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 36 ms 980 KB Output is correct
14 Correct 32 ms 980 KB Output is correct
15 Correct 7 ms 996 KB Output is correct
16 Correct 27 ms 1000 KB Output is correct
17 Correct 33 ms 980 KB Output is correct
18 Correct 14 ms 1016 KB Output is correct
19 Correct 21 ms 992 KB Output is correct
20 Correct 12 ms 980 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 23 ms 980 KB Output is correct
23 Correct 20 ms 1004 KB Output is correct
24 Correct 28 ms 980 KB Output is correct
25 Correct 795 ms 56844 KB Output is correct
26 Correct 775 ms 56716 KB Output is correct
27 Correct 840 ms 57308 KB Output is correct
28 Correct 746 ms 56548 KB Output is correct
29 Correct 569 ms 57800 KB Output is correct
30 Correct 751 ms 60448 KB Output is correct
31 Correct 424 ms 60488 KB Output is correct
32 Correct 471 ms 56420 KB Output is correct
33 Correct 419 ms 56568 KB Output is correct
34 Correct 729 ms 58296 KB Output is correct
35 Correct 659 ms 58288 KB Output is correct
36 Correct 1912 ms 57136 KB Output is correct
37 Execution timed out 2086 ms 57928 KB Time limit exceeded
38 Halted 0 ms 0 KB -