제출 #676836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676836		abysmal	Railway Trip 2 (JOI22_ho_t4)	C++14	27 / 100	2081 ms	60636 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<deque>
#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 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();

//        for(int i = 0; i < LOG; i++)
//        {
//            cout << "i = " << i << "\n";
//            for(int j = 0; j < n; j++)
//            {
//                cout << range[i][j].first << " " << range[i][j].second << "\n";
//            }
//            cout << "\n";
//        }

        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);
        }
//        cerr << "l = " << l << " ; r = " << r << "\n";
//        cerr << "t = " << t << "\n";
        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);
        }

        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;
        }

        while(!dq.empty()) dq.pop_back();

        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = 0; j < (int) b[i].size(); j++)
            {
                int v = b[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].first = dq.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";
            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: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13