oj.uz

답안 #898111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898111 2024-01-04T10:17:25 Z vjudge1 Passport (JOI23_passport) C++17
6 / 100
 163 ms 7648 KB 
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()

#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl;

#define printmp(a)    \
    for (auto &x : a) \
        cout << x.fs << " " << x.ss << endl;

const int mod = 998244353;

struct SegmentTree
{
    vector<int> tree;
    int size;

    int merge(int a, int b)
    {
        return a + b;
    }

    int single()
    {
        return 1e9;
    }

    void init(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        tree.resize(2 * size, 1e9);
    }

    void build(int n, int x, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            tree[x] = single();
            return;
        }
        int m = (lx + rx) / 2;
        build(n, 2 * x + 1, lx, m);
        build(n, 2 * x + 2, m, rx);
        tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void build(int n)
    {
        build(n, 0, 0, size);
    }

    void set(int l, int r, int v, int x, int lx, int rx)
    {
        if (l <= lx and rx <= r)
        {
            tree[x] = min(tree[x], v);
            return;
        }
        if (rx <= l or r <= lx)
            return;
        int m = (lx + rx) / 2;
        set(l, r, v, 2 * x + 1, lx, m);
        set(l, r, v, 2 * x + 2, m, rx);
    }

    void set(int l, int r, int v)
    {
        set(l, r, v, 0, 0, size);
    }

    int sum(int i, int s, int x, int lx, int rx)
    {
        s = min(s, tree[x]);
        if (rx - lx == 1)
            return s;
        int m = (lx + rx) / 2;
        if (i < m)
            s = sum(i, s, 2 * x + 1, lx, m);
        else
            s = sum(i, s, 2 * x + 2, m, rx);
        return s;
    }

    int sum(int i)
    {
        return sum(i, 1e9, 0, 0, size);
    }
};

void solve(){
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i].fs >> a[i].ss;
    int q;
    cin >> q;
    for(int i = 0; i < q; i ++){
        int x;
        cin >> x;
        if(x != 1){
            vector<int> k(n, 1e9);
            k[x - 1] = 0;
            int l = x - 1, r = x - 1;
            while (l >= 0 or r < n)
            {
                if (r == n or (l >= 0 and k[l] <= k[r]))
                {
                    for (int j = a[l].fs - 1; j <= a[l].ss - 1; j++)
                        k[j] = min(k[j], k[l] + 1);
                    l--;
                }
                else
                {
                    for (int j = a[r].fs - 1; j <= a[r].ss - 1; j++)
                        k[j] = min(k[j], k[r] + 1);
                    r++;
                }
            }
            x = *max_element(all(k));
            if (x != 1e9)
                cout << x << endl;
            else
                cout << -1 << endl;
            continue;
        }
        SegmentTree s;
        s.init(n);
        int l = x, r = x, mxl = a[x - 1].fs, mxr = a[x - 1].ss;
        s.set(x - 1, x, 0);
        int ans = 0;
        while(mxl <= l or r <= mxr){
            int left = (l < mxl ? 1e9 : s.sum(l - 1)), right = (r > mxr ? 1e9 : s.sum(r - 1));
            if(r > mxr or (mxl <= l and left <= right)){
                s.set(a[l - 1].fs - 1, a[l - 1].ss, left + 1);
                mxl = min(mxl, a[l - 1].fs);
                mxr = max(mxr, a[l - 1].ss);
                l --;
            }
            else{
                s.set(a[r - 1].fs - 1, a[r - 1].ss, right + 1);
                mxl = min(mxl, a[r - 1].fs);
                mxr = max(mxr, a[r - 1].ss);
                r ++;
            }
        }
        for(int i = 1; i <= n; i ++)
            ans = max(ans, s.sum(i - 1));
        if(l == 0 and r == n + 1)
            cout << ans << endl;
        else
            cout << -1 << endl;
    }
}

signed main()
{
    // fastio
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        // cout << endl;
    }
}

Compilation message

passport.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast")
      | 
passport.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("Ofast")
      | 
passport.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize(Ofast)
      |

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 163 ms 7596 KB Output is correct
5 Correct 128 ms 7616 KB Output is correct
6 Correct 119 ms 7648 KB Output is correct
7 Correct 102 ms 7568 KB Output is correct
8 Correct 75 ms 6736 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 163 ms 7596 KB Output is correct
5 Correct 128 ms 7616 KB Output is correct
6 Correct 119 ms 7648 KB Output is correct
7 Correct 102 ms 7568 KB Output is correct
8 Correct 75 ms 6736 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -