Submission #898091

#	Time	Username	Problem	Language	Result	Execution time	Memory
898091		vjudge1	Misspelling (JOI22_misspelling)	C++17	0 / 100	1 ms	348 KiB

misspelling

#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;
        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 (stderr)

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

• Subtask 1: 0 / 8
• Subtask 2: 0 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11