oj.uz

답안 #676844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676844 2023-01-01T10:45:39 Z abysmal Railway Trip 2 (JOI22_ho_t4) C++14
27 / 100
 2000 ms 47340 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;
    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));
        vector<pair<int, int> > p(n, make_pair(-1, -1));
        for(int i = 0; i < n; i++)
        {
            p[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;

            p[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;

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

        for(int i = 0; i < n; i++)
        {
            treel[0][sz + i] = p[i].first;
            treer[0][sz + i] = p[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 = p[j].first;
                int r = p[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, newr);

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

    void update(int& id, int& d, int& min_, int& max_)
    {
        treel[d][sz + id] = min(treel[d][sz + id], min_);
        treer[d][sz + id] = max(treer[d][sz + id], max_);

        for(int i = (sz + id) / 2; i >= 1; i /= 2)
        {
            treel[d][i] = min(treel[d][i * 2], treel[d][i * 2 + 1]);
            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

# 결과 실행 시간 메모리 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 2 ms 340 KB Output is correct
6 Correct 2 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 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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 2 ms 340 KB Output is correct
6 Correct 2 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 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 37 ms 724 KB Output is correct
14 Correct 34 ms 724 KB Output is correct
15 Correct 7 ms 828 KB Output is correct
16 Correct 30 ms 724 KB Output is correct
17 Correct 34 ms 852 KB Output is correct
18 Correct 11 ms 852 KB Output is correct
19 Correct 21 ms 836 KB Output is correct
20 Correct 14 ms 724 KB Output is correct
21 Correct 3 ms 836 KB Output is correct
22 Correct 21 ms 724 KB Output is correct
23 Correct 19 ms 832 KB Output is correct
24 Correct 28 ms 840 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 766 ms 43532 KB Output is correct
2 Correct 725 ms 43592 KB Output is correct
3 Correct 801 ms 44012 KB Output is correct
4 Correct 718 ms 43324 KB Output is correct
5 Correct 535 ms 44488 KB Output is correct
6 Correct 721 ms 47340 KB Output is correct
7 Correct 411 ms 47256 KB Output is correct
8 Correct 421 ms 43380 KB Output is correct
9 Correct 373 ms 43220 KB Output is correct
10 Correct 693 ms 45004 KB Output is correct
11 Correct 621 ms 45016 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1831 ms 43780 KB Output is correct
2 Execution timed out 2088 ms 44932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2089 ms 43768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 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 2 ms 340 KB Output is correct
6 Correct 2 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 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 37 ms 724 KB Output is correct
14 Correct 34 ms 724 KB Output is correct
15 Correct 7 ms 828 KB Output is correct
16 Correct 30 ms 724 KB Output is correct
17 Correct 34 ms 852 KB Output is correct
18 Correct 11 ms 852 KB Output is correct
19 Correct 21 ms 836 KB Output is correct
20 Correct 14 ms 724 KB Output is correct
21 Correct 3 ms 836 KB Output is correct
22 Correct 21 ms 724 KB Output is correct
23 Correct 19 ms 832 KB Output is correct
24 Correct 28 ms 840 KB Output is correct
25 Correct 766 ms 43532 KB Output is correct
26 Correct 725 ms 43592 KB Output is correct
27 Correct 801 ms 44012 KB Output is correct
28 Correct 718 ms 43324 KB Output is correct
29 Correct 535 ms 44488 KB Output is correct
30 Correct 721 ms 47340 KB Output is correct
31 Correct 411 ms 47256 KB Output is correct
32 Correct 421 ms 43380 KB Output is correct
33 Correct 373 ms 43220 KB Output is correct
34 Correct 693 ms 45004 KB Output is correct
35 Correct 621 ms 45016 KB Output is correct
36 Correct 1831 ms 43780 KB Output is correct
37 Execution timed out 2088 ms 44932 KB Time limit exceeded
38 Halted 0 ms 0 KB -