oj.uz

Submission #898053

# Submission time Handle Problem Language Result Execution time Memory
898053 2024-01-04T09:14:50 Z vjudge1 Passport (JOI23_passport) C++17
6 / 100
 93 ms 9052 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 printtree()
    {
        print(tree)
    }
};

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;
        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);
        while(mxl <= l or r <= mxr){
            while(l >= 1 and mxl <= l){
                s.set(a[l - 1].fs - 1, a[l - 1].ss, s.sum(l - 1) + 1);
                mxl = min(mxl, a[l - 1].fs);
                mxr = max(mxr, a[l - 1].ss);
                l --;
            }
            while(r <= n and mxr >= r){
                s.set(a[r - 1].fs - 1, a[r - 1].ss, s.sum(r - 1) + 1);
                mxl = min(mxl, a[r - 1].fs);
                mxr = max(mxr, a[r - 1].ss);
                r++;
            }
        }
        int ans = 0;
        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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 93 ms 9052 KB Output is correct
5 Correct 69 ms 9040 KB Output is correct
6 Correct 64 ms 9036 KB Output is correct
7 Correct 49 ms 8632 KB Output is correct
8 Correct 34 ms 8032 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 93 ms 9052 KB Output is correct
5 Correct 69 ms 9040 KB Output is correct
6 Correct 64 ms 9036 KB Output is correct
7 Correct 49 ms 8632 KB Output is correct
8 Correct 34 ms 8032 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -