Submission #676821

#	Time	Username	Problem	Language	Result	Execution time	Memory
676821		abysmal	Railway Trip 2 (JOI22_ho_t4)	C++14	11 / 100	2071 ms	66308 KiB

Main

#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
• Subtask 2: 0 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13