Submission #647364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
647364	2022-10-02T09:54:37 Z	dxz05	Segments (IZhO18_segments)	C++14	16 / 100	210 ms	17308 KB

segments

//#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair

clock_t startTime;

int getCurrentTime() {
    return int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000);
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e6 + 3e2;
const int M = 5555;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using indexed_multiset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

indexed_multiset<pair<ll, int>> lfs, rgs;

multiset<pair<int, int>> seg;
vector<pair<int, int>> vec_seg;

void add(int l, int r, int id){
    seg.insert(MP(l, r));
    vec_seg.emplace_back(l, r);
    lfs.insert(MP(l, id));
    rgs.insert(MP(r, id));
}

void del(int l, int r, int id){
    seg.erase(seg.find(MP(l, r)));
    lfs.erase(lfs.find(MP(l, id)));
    rgs.erase(rgs.find(MP(r, id)));
}

int intersects(ll l, ll r, ll k){
    int res = (int)seg.size();

    int strictly_left = rgs.order_of_key(MP(l + k - 1, -1));
    int strictly_right = lfs.size() - lfs.order_of_key(MP(r - k + 2, -1));

    res -= strictly_left;
    res -= strictly_right;

    return res;
}

void solve(int TC){
    int n, t;
    cin >> n >> t;

    int lastans = 0;

    int next_id = 0;
    while (n--){
        int op;
        cin >> op;
        if (op == 1){
            int l, r;
            cin >> l >> r;

            l ^= (t * lastans);
            r ^= (t * lastans);
            if (l > r) swap(l, r);

            add(l, r, next_id);
            next_id++;

            debug('+', l, r);
        }
        if (op == 2){
            int id;
            cin >> id;
            --id;
            int l = vec_seg[id].first, r = vec_seg[id].second;
            del(l, r, id);

            debug('-', l, r);
        }
        if (op == 3){
            int l, r, k;
            cin >> l >> r >> k;

            l ^= (t * lastans);
            r ^= (t * lastans);
            if (l > r) swap(l, r);

            int ans = 0;

            if (r - l + 1 >= k){
                ans = intersects(l, r, k);
            }

            cout << ans << endl;

            lastans = ans;

            debug('?', l, r);
        }
    }

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

#ifdef dddxxz
    cerr << endl << "Time: " << getCurrentTime() << " ms" << endl;
#endif

    return 0;
}

Compilation message

segments.cpp: In function 'void solve(int)':
segments.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
segments.cpp:101:13: note: in expansion of macro 'debug'
  101 |             debug('+', l, r);
      |             ^~~~~
segments.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
segments.cpp:110:13: note: in expansion of macro 'debug'
  110 |             debug('-', l, r);
      |             ^~~~~
segments.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
segments.cpp:130:13: note: in expansion of macro 'debug'
  130 |             debug('?', l, r);
      |             ^~~~~

Subtask #1
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Incorrect	4 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	208 ms	9712 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	1088 KB	Output is correct
2	Correct	83 ms	1052 KB	Output is correct
3	Correct	99 ms	1172 KB	Output is correct
4	Correct	91 ms	1004 KB	Output is correct
5	Correct	210 ms	13328 KB	Output is correct
6	Correct	181 ms	11376 KB	Output is correct
7	Correct	198 ms	12584 KB	Output is correct
8	Correct	204 ms	17308 KB	Output is correct
9	Correct	184 ms	16488 KB	Output is correct
10	Correct	189 ms	12508 KB	Output is correct
11	Correct	122 ms	1688 KB	Output is correct
12	Correct	204 ms	12528 KB	Output is correct
13	Correct	170 ms	11312 KB	Output is correct
14	Correct	153 ms	5824 KB	Output is correct
15	Correct	136 ms	4944 KB	Output is correct
16	Correct	134 ms	3676 KB	Output is correct
17	Correct	199 ms	9516 KB	Output is correct
18	Correct	190 ms	9536 KB	Output is correct
19	Correct	187 ms	9672 KB	Output is correct
20	Correct	187 ms	9680 KB	Output is correct
21	Correct	127 ms	1892 KB	Output is correct
22	Correct	146 ms	6984 KB	Output is correct
23	Correct	167 ms	9812 KB	Output is correct
24	Correct	163 ms	7512 KB	Output is correct
25	Correct	88 ms	1020 KB	Output is correct
26	Correct	86 ms	1016 KB	Output is correct
27	Correct	92 ms	1056 KB	Output is correct
28	Correct	92 ms	960 KB	Output is correct
29	Correct	163 ms	10560 KB	Output is correct
30	Correct	203 ms	10628 KB	Output is correct
31	Correct	190 ms	16656 KB	Output is correct
32	Correct	186 ms	12584 KB	Output is correct
33	Correct	166 ms	11608 KB	Output is correct
34	Correct	126 ms	4896 KB	Output is correct
35	Correct	154 ms	9068 KB	Output is correct
36	Correct	175 ms	12160 KB	Output is correct