제출 #379143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379143		2qbingxuan	Segments (IZhO18_segments)	C++14	7 / 100	329 ms	65540 KiB

segments

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
using namespace __gnu_pbds;
template <typename T> using rbt = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef int64_t ll;

constexpr ll maxn = 100025, INF = 1e18, MOD = 998244353, K = 14699, inf = 1e9;
const int maxc = 2e9;

struct Tree1D {
    rbt<pair<int,int>> pbds;
    int tot;
    void add(int p, int d) {
        if (d == 1)
            pbds.insert({ p, tot++ });
        else if (d == -1)
            pbds.erase(pbds.lower_bound({ p, 0 }));
    }
    int query(int p) {
        return pbds.order_of_key({ p+1, 0 });
    }
} len;

struct Fenwick2D {
    unordered_map<int, rbt<pair<int,int>>> b;
    Fenwick2D() { b.reserve(1048576), b.max_load_factor(0.25); }
    int tot;
    void add(ll x, int y, int k) {
        for (; x < maxc; x += x & -x) {
            if (k == 1)
                b[x].insert({ y, tot++ });
            else if (k == -1)
                b[x].erase(b[x].lower_bound({ y, 0 }));
        }
    }
    int query(ll x, int y) {
        int res = 0;
        for (; x > 0; x -= x & -x)
            res += b[x].order_of_key({ y+1, 0 }); // how many <= y
        return res;
    }
} tl, tr;

pair<int,int> seg[maxn];
int segId = 0;
void add(int l, int r, int d) {
    len.add(maxc-5 - (r - l), d);
    tl.add(maxc-5 - (r - l), r, d);
    tr.add(maxc-5 - (r - l), maxc-5 - l, d);
}

// bool dead[maxn];
int query(int l, int r, int k) {
    return len.query(maxc-5 - k) - tl.query(maxc-5 - k, l + k - 1) - tr.query(maxc-5 - k, maxc-5 - (r - k + 1));
    /*
    int res = 0;
    for (int i = 0; i < segId; i++) {
        if (dead[i]) continue;
        auto [nl, nr] = seg[i];
        if (nr - nl >= k) {
            ++res;
            if (nr < l + k) --res;
            if (nl > r - k) --res;
        }
    }
    return res;
    */
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, encode;
    cin >> n >> encode;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            if (encode) a ^= ans, b ^= ans;
            if (a > b) swap(a, b);
            ++b;
            add(a, b, 1);
            seg[segId++] = { a, b };
        } else if (t == 2) {
            int id;
            cin >> id;
            --id;
            auto [a, b] = seg[id];
            add(a, b, -1);
            // dead[id] = true;
        } else if (t == 3) {
            int a, b, k;
            cin >> a >> b >> k;
            if (encode) a ^= ans, b ^= ans;
            if (a > b) swap(a, b);
            ++b;
            ans = query(a, b, k);
            cout << ans << '\n';
        }
    }
}
/*
6 1
1 1 2
3 2 4 2
1 3 5 
3 2 3 1
2 1 
3 0 3 1

6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
 */

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      | 
segments.cpp: In function 'int main()':
segments.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |             auto [a, b] = seg[id];
      |                  ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25