为什么同样的代码开了O2优化之后就ac不了了?
查看原帖
为什么同样的代码开了O2优化之后就ac不了了?
633322
AC_hqy楼主2023/2/16 22:02
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    #include <cmath>
    #include <cstdio>
    #include <map>
    #include <set>
    #define x first
    #define y second
    #define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    #define endl '\n'
    #define int long long
    
    using namespace std;
    
    const int N = 5e5 + 10;
    
    struct Node
    {
        int l, r,v;
        bool flag;
    }tr[N << 2];
    int n, m, idx = 0, w[N];
    map<int, int> ys, yd;
    vector<int> temp;
    
    void pushup(int u)
    {
        tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
        tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
        if (ys[tr[u << 1].r] != ys[tr[u << 1 | 1].l] - 1) tr[u].flag = false;
    }
    
    void build(int u, int l, int r)
    {
        if (l == r) tr[u] = {l, r, w[r], true};
        else
        {
            tr[u] = {l, r};
            int mid = l + r >> 1;
            build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }
    
    Node query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u];
        int mid = tr[u].l + tr[u].r >> 1;
        Node left = {0, 0, 0, 1}, right = {0, 0, 0, 1};
        if (l <= mid) left = query(u << 1, l, r);
        if (r > mid) right = query(u << 1 | 1, l, r);
        Node root;
        root.v = max(left.v, right.v);
        root.flag = left.flag & right.flag;
        if (left.l && right.l)
        {
            if (ys[left.r] != ys[right.l] - 1) root.flag = false;
        }
        return root;
    }
    
    int find(int x)
    {
        int l = 0, r = temp.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (temp[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (temp[r] < x) return -2e9;
        return temp[r];
    }
    
    int find_(int x)
    {
        int l = 0, r = temp.size() - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (temp[mid] <= x) l = mid;
            else r = mid - 1;
        }
        if (temp[r] > x) return -2e9;
        return temp[r];
    }
    
    void solve()
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int year, x;
            cin >> year >> x;
            ys[++idx] = year;
            yd[year] = idx;
            w[idx] = x;
            temp.push_back(year);
        }
        build(1, 1, idx);
        cin >> m;
        while (m--)
        {
            int y, x;
            cin >> y >> x;
            int l = y + 1, r = x - 1;
            if (!yd[l]) l = find(l);
            if (!yd[r]) r = find_(r);
            // cout << l << " " << r << endl;
            if (l == -2e9 || r == -2e9)
            {
                if (yd[y] && yd[x])
                {
                    if (w[yd[x]] > w[yd[y]]) cout << "false" << endl;
                    else cout << "maybe" << endl;
                }
                else cout << "maybe" << endl;
            }
           else if (r < l) 
            {   
                if (yd[y] && yd[x])
                {
                    if (w[yd[x]] > w[yd[y]]) cout << "false" << endl;
                    else if (!yd[y + 1] || !yd[x - 1]) cout << "maybe" << endl;
                    else cout << "true" << endl;
                }
                else if (!yd[y] || !yd[x]) cout << "maybe" << endl;
            }
            else
            {   
                auto t = query(1, yd[l], yd[r]);
                if (yd[y] && yd[x])
                {
                    // cout << t.v << endl;
                    if (w[yd[x]] > w[yd[y]] || t.v >= w[yd[x]]) cout << "false" << endl;
                    else if (!yd[y + 1] || !yd[x - 1] || !t.flag) cout << "maybe" << endl;
                    else cout << "true" << endl;
                }
                else if (yd[y]) 
                {
                    if (t.v >= w[yd[y]]) cout << "false" << endl;
                    else cout << "maybe" << endl;
                }
                else if (yd[x])
                {  
                    if ( t.v >= w[yd[x]]) cout << "false" << endl;
                    else cout << "maybe" << endl;
                }
                else cout << "maybe" << endl;
            }
        }
    }
    
    signed main() {
        // IOS;
        solve();
      return 0;
    }
2023/2/16 22:02
加载中...