Submission #647359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
647359	2022-10-02T09:48:18 Z	dxz05	Segments (IZhO18_segments)	C++14	16 / 100	264 ms	17352 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<int, 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(int l, int r, int 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	5 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	229 ms	9592 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	109 ms	1036 KB	Output is correct
2	Correct	88 ms	1028 KB	Output is correct
3	Correct	95 ms	1304 KB	Output is correct
4	Correct	84 ms	1000 KB	Output is correct
5	Correct	206 ms	13296 KB	Output is correct
6	Correct	204 ms	11416 KB	Output is correct
7	Correct	200 ms	12584 KB	Output is correct
8	Correct	196 ms	17352 KB	Output is correct
9	Correct	200 ms	16556 KB	Output is correct
10	Correct	203 ms	12480 KB	Output is correct
11	Correct	116 ms	1616 KB	Output is correct
12	Correct	179 ms	12608 KB	Output is correct
13	Correct	201 ms	11372 KB	Output is correct
14	Correct	141 ms	5920 KB	Output is correct
15	Correct	147 ms	4996 KB	Output is correct
16	Correct	151 ms	3656 KB	Output is correct
17	Correct	197 ms	9584 KB	Output is correct
18	Correct	212 ms	9568 KB	Output is correct
19	Correct	199 ms	9604 KB	Output is correct
20	Correct	205 ms	9624 KB	Output is correct
21	Correct	125 ms	1876 KB	Output is correct
22	Correct	162 ms	7080 KB	Output is correct
23	Correct	176 ms	10024 KB	Output is correct
24	Correct	264 ms	7504 KB	Output is correct
25	Correct	102 ms	1052 KB	Output is correct
26	Correct	86 ms	1004 KB	Output is correct
27	Correct	95 ms	1024 KB	Output is correct
28	Correct	85 ms	968 KB	Output is correct
29	Correct	196 ms	10688 KB	Output is correct
30	Correct	180 ms	10580 KB	Output is correct
31	Correct	208 ms	16692 KB	Output is correct
32	Correct	216 ms	12640 KB	Output is correct
33	Correct	190 ms	11560 KB	Output is correct
34	Correct	182 ms	4932 KB	Output is correct
35	Correct	181 ms	9128 KB	Output is correct
36	Correct	185 ms	12152 KB	Output is correct