Submission #646968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646968	2022-10-01T09:13:37 Z	dxz05	Segments (IZhO18_segments)	C++14	16 / 100	253 ms	19600 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 res = (int)seg.size();

    int strictly_left = rgs.order_of_key(MP(l, 0)); // number of right-points with < l
    int strictly_right = lfs.size() - lfs.order_of_key(MP(r + 1, 0)); // number of left-points with > r

    return res - strictly_left - strictly_right;
}

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 = intersects(l, r);

            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:98:13: note: in expansion of macro 'debug'
   98 |             debug('+', l, r);
      |             ^~~~~
segments.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
segments.cpp:107:13: note: in expansion of macro 'debug'
  107 |             debug('-', l, r);
      |             ^~~~~
segments.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
segments.cpp:123:13: note: in expansion of macro 'debug'
  123 |             debug('?', l, r);
      |             ^~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	233 ms	9928 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	114 ms	1324 KB	Output is correct
2	Correct	108 ms	1960 KB	Output is correct
3	Correct	144 ms	1952 KB	Output is correct
4	Correct	101 ms	1976 KB	Output is correct
5	Correct	219 ms	14752 KB	Output is correct
6	Correct	253 ms	13728 KB	Output is correct
7	Correct	202 ms	14628 KB	Output is correct
8	Correct	229 ms	19600 KB	Output is correct
9	Correct	210 ms	18808 KB	Output is correct
10	Correct	183 ms	14308 KB	Output is correct
11	Correct	127 ms	3568 KB	Output is correct
12	Correct	197 ms	14572 KB	Output is correct
13	Correct	192 ms	13120 KB	Output is correct
14	Correct	148 ms	7716 KB	Output is correct
15	Correct	140 ms	6976 KB	Output is correct
16	Correct	144 ms	5496 KB	Output is correct
17	Correct	214 ms	11900 KB	Output is correct
18	Correct	222 ms	11988 KB	Output is correct
19	Correct	225 ms	11896 KB	Output is correct
20	Correct	190 ms	11844 KB	Output is correct
21	Correct	143 ms	3760 KB	Output is correct
22	Correct	158 ms	9060 KB	Output is correct
23	Correct	200 ms	11764 KB	Output is correct
24	Correct	161 ms	9572 KB	Output is correct
25	Correct	97 ms	2928 KB	Output is correct
26	Correct	97 ms	2848 KB	Output is correct
27	Correct	91 ms	2916 KB	Output is correct
28	Correct	90 ms	2828 KB	Output is correct
29	Correct	226 ms	12632 KB	Output is correct
30	Correct	182 ms	12756 KB	Output is correct
31	Correct	203 ms	18924 KB	Output is correct
32	Correct	200 ms	14408 KB	Output is correct
33	Correct	204 ms	13436 KB	Output is correct
34	Correct	138 ms	6708 KB	Output is correct
35	Correct	167 ms	11052 KB	Output is correct
36	Correct	202 ms	13996 KB	Output is correct