Submission #379331

#	Time	Username	Problem	Language	Result	Execution time	Memory
379331		2qbingxuan	Segments (IZhO18_segments)	C++14	75 / 100	5060 ms	28328 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;

const int maxc = 2e9, inf = 1e9, K1 = 1024, K2 = 450, maxn = 200025;

pair<int,int> seg[maxn];
int segId = 0;

vector<tuple<int,int,int>> recent, total;
vector<tuple<int,int,int>> block[maxn];
int minLen[maxn], blockCnt;
vector<int> lens;

struct StaticPrefixSum {
    vector<pair<int,int>> st;
    int query(int x) {
        auto it = lower_bound(st.begin(), st.end(), make_pair(x, -inf));
        if (it == st.begin()) return 0;
        return prev(it) -> second;
    }
    void add(int p, int v) {
        st.emplace_back(p, v);
    }
    void clear() {
        st.clear();
    }
    void build() {
        sort(st.begin(), st.end());
        int it = 0;
        for (int i = 1; i < st.size(); i++) {
            if (st[i].first != st[it].first) {
                st[++it] = st[i];
            } else {
                st[it].second += st[i].second;
            }
        }
        st.resize(it+1);
        for (int i = 1; i < st.size(); i++) st[i].second += st[i-1].second;
    }
} lpref[maxn], rpref[maxn];
int totSum[maxn];

void build() {
    sort(lens.begin(), lens.end(), greater<int>());
    lens.erase(unique(lens.begin(), lens.end()), lens.end());

    for (int i = 0; i < lens.size(); i++) minLen[i / K2] = lens[i];
    blockCnt = lens.size() / K2 + 1;
    for (int i = 0; i < blockCnt; i++) {
        block[i].clear();
        lpref[i].clear();
        rpref[i].clear();
        totSum[i] = 0;
    }
    for (auto [l, r, v]: total) {
        int id = lower_bound(lens.begin(), lens.end(), r - l, greater<int>()) - lens.begin();
        int bid = id / K2;
        block[id / K2].emplace_back(l, r, v);
        lpref[id / K2].add(-l, v);
        rpref[id / K2].add(r, v);
        totSum[id / K2] += v;
    }
    for (int i = 0; i < blockCnt; i++) lpref[i].build(), rpref[i].build();
}

void add(int l, int r, int d) {
    recent.emplace_back(l, r, d);
    if (recent.size() == K1) {
        for (auto [l, r, v]: recent) {
            lens.emplace_back(r - l);
            total.emplace_back(l, r, v);
        }
        recent.clear();
        build();
    }
}

int query(int l, int r, int k) {
    int res = 0;
    for (int i = 0; i < blockCnt; i++) {
        debug(i);
        for (auto [nl, nr, v]: block[i])
            debug(nl, nr, v);
        debug(minLen[i], k);
        if (minLen[i] >= k) {
            debug(totSum[i], rpref[i].query(l + k), lpref[i].query(-(r - k)));
            res += totSum[i] - rpref[i].query(l + k) - lpref[i].query(-(r - k));
            debug(res);
        } else {
            for (auto [nl, nr, v]: block[i]) {
                if (nr - nl >= k) {
                    res += v;
                    if (nr < l + k) res -= v;
                    if (nl > r - k) res -= v;
                }
            }
            break;
        }
    }
    for (auto [nl, nr, v]: recent) {
        if (nr - nl >= k) {
            res += v;
            if (nr < l + k) res -= v;
            if (nl > r - k) res -= v;
        }
    }
    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);
        } 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
 */

Compilation message (stderr)

segments.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      | 
segments.cpp: In member function 'void StaticPrefixSum::build()':
segments.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i = 1; i < st.size(); i++) {
      |                         ~~^~~~~~~~~~~
segments.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 1; i < st.size(); i++) st[i].second += st[i-1].second;
      |                         ~~^~~~~~~~~~~
segments.cpp: In function 'void build()':
segments.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < lens.size(); i++) minLen[i / K2] = lens[i];
      |                     ~~^~~~~~~~~~~~~
segments.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [l, r, v]: total) {
      |               ^
segments.cpp:75:13: warning: unused variable 'bid' [-Wunused-variable]
   75 |         int bid = id / K2;
      |             ^~~
segments.cpp: In function 'void add(int, int, int)':
segments.cpp:87:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         for (auto [l, r, v]: recent) {
      |                   ^
segments.cpp: In function 'int query(int, int, int)':
segments.cpp:100:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |         for (auto [nl, nr, v]: block[i])
      |                   ^
segments.cpp:100:19: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  100 |         for (auto [nl, nr, v]: block[i])
      |                   ^~~~~~~~~~~
segments.cpp:108:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |             for (auto [nl, nr, v]: block[i]) {
      |                       ^
segments.cpp:118:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for (auto [nl, nr, v]: recent) {
      |               ^
segments.cpp: In function 'int main()':
segments.cpp:148:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |             auto [a, b] = seg[id];
      |                  ^

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