oj.uz

Submission #676821

# Submission time Handle Problem Language Result Execution time Memory
676821 2023-01-01T09:13:55 Z abysmal Railway Trip 2 (JOI22_ho_t4) C++14
11 / 100
 2000 ms 66308 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>

using namespace std;

const int64_t INF = (int64_t) 4 * 1e5 + 5;
const int64_t mINF = 20;
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 Edge
{
    int u;
    int v;
    int w;

    Edge(int u_, int v_, int w_) : u(u_), v(v_), w(w_) {}

    bool operator < (const Edge& o) const
    {
        return w < o.w;
    }
};

struct Thing
{
    int l;
    int r;

    Thing(int l_, int r_) : l(l_), r(r_) {}

    bool operator < (const Thing& o) const
    {
        if(r == o.r) return l < o.l;
        return r < o.r;
    }
};

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 = 0;
            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()
    {
        set<Thing> s;
        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);
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < (int) a[i].size(); j++)
            {
                int v = a[i][j];

                s.insert(Thing(i, -v));
            }

            if(i - k >= 0)
            {
                int u = i - k;
                for(int j = 0; j < (int) a[u].size(); j++)
                {
                    int v = a[u][j];

                    s.erase(Thing(u, -v));
                }
            }

            if(s.empty()) continue;
            Thing tmp = *(s.begin());

            range[0][i].second = -tmp.r;
        }

        s.clear();
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = 0; j < (int) b[i].size(); j++)
            {
                int v = b[i][j];

                s.insert(Thing(i, v));
            }

            if(i + k < n)
            {
                int u = i + k;
                for(int j = 0; j < (int) b[u].size(); j++)
                {
                    int v = b[u][j];

                    s.erase(Thing(u, v));
                }
            }

            if(s.empty()) continue;
            Thing tmp = *(s.begin());

            range[0][i].first = tmp.r;
        }

        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";
            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, i - 1, 0);
                int newr = get(1, 0, sz - 1, l, r, i - 1, 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 320 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 320 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 57788 KB Output is correct
2 Correct 803 ms 57800 KB Output is correct
3 Correct 895 ms 58416 KB Output is correct
4 Correct 778 ms 57476 KB Output is correct
5 Correct 659 ms 61604 KB Output is correct
6 Correct 784 ms 62864 KB Output is correct
7 Correct 528 ms 66308 KB Output is correct
8 Correct 521 ms 58180 KB Output is correct
9 Correct 454 ms 59164 KB Output is correct
10 Correct 777 ms 60600 KB Output is correct
11 Correct 759 ms 64384 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 62032 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 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 320 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -