oj.uz

답안 #676862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676862 2023-01-01T11:28:00 Z abysmal Railway Trip 2 (JOI22_ho_t4) C++14
44 / 100
 1427 ms 49864 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 = s;
            int r = s;
            int ans = 0;
            for(int j = LOG - 1; j >= 0; j--)
            {
                int newl = get(1, 0, sz - 1, l, r, j, 0);
                int newr = get(1, 0, sz - 1, l, r, j, 1);

                if(t > newr || t < newl)
                {
                    ans += MASK(j);

                    l = newl;
                    r = newr;
                }
            }

            int x = get(1, 0, sz - 1, s, s, LOG - 1, 0);
            int y = get(1, 0, sz - 1, s, s, LOG - 1, 1);

            if(t < x || t > y) cout << "-1\n";
            else cout << ans + 1 << "\n";
        }
    }

    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++)
        {
            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);

                update(j, i, newl, newr);

                p[j] = make_pair(newl, newr);
            }
        }
    }

    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 2 ms 424 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 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 1 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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 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 1 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 Incorrect 15 ms 840 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 948 ms 43536 KB Output is correct
2 Correct 898 ms 43488 KB Output is correct
3 Correct 938 ms 44012 KB Output is correct
4 Correct 764 ms 43328 KB Output is correct
5 Correct 647 ms 44584 KB Output is correct
6 Correct 850 ms 47256 KB Output is correct
7 Correct 439 ms 47256 KB Output is correct
8 Correct 424 ms 43252 KB Output is correct
9 Correct 412 ms 43208 KB Output is correct
10 Correct 718 ms 44864 KB Output is correct
11 Correct 695 ms 45012 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 854 ms 43596 KB Output is correct
2 Correct 909 ms 44708 KB Output is correct
3 Correct 1354 ms 46136 KB Output is correct
4 Correct 651 ms 49864 KB Output is correct
5 Correct 708 ms 47400 KB Output is correct
6 Correct 642 ms 47404 KB Output is correct
7 Correct 1052 ms 48056 KB Output is correct
8 Correct 1012 ms 48000 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1207 ms 43808 KB Output is correct
2 Incorrect 1427 ms 46068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 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 1 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 Incorrect 15 ms 840 KB Output isn't correct
14 Halted 0 ms 0 KB -