Submission #495755

#TimeUsernameProblemLanguageResultExecution timeMemory
495755IerusSegments (IZhO18_segments)C++17
0 / 100
5057 ms5716 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #pragma GCC optimize ("unroll-loops,Ofast,O3") #pragma GCC target("avx,avx2,fma") #define F first #define S second #define sz(x) (int)x.size() #define pb push_back #define eb emplace_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ; #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> typedef long long ll; const int E = 1e6+777; const long long inf = 1e18+777; const int N = 1e5+777; const int MOD = 1e9+7; int que, t, last, tim; pair<int,int> pr[N]; ordered_set st; int get(int L, int R, int k, int res = 0){ for(auto[x, y] : st){ int l1, r1, l2, r2; if(x < L){ l1 = x, r1 = y, l2 = L, r2 = R; }else{ l1 = L, r1 = R, l2 = x, r2 = y; } int cur = max(0, min(r1, r2) - max(l1, l2) + 1); if(cur >= k) ++res; } return res; } int main(){NFS; cin >> que >> t; for(int type; que--;){ cin >> type; if(type == 1){ int a, b; cin >> a >> b; a = (a ^ (t * last)); b = (b ^ (t * last)); if(a > b)swap(a, b); pr[++tim] = {a, b}; st.insert({a, b}); }else if(type == 2){ int id; cin >> id; st.erase(pr[id]); }else{ int l, r, k; cin >> l >> r >> k; l = (l ^ (t * last)); r = (r ^ (t * last)); if(l > r) swap(l, r); if(k == 1){ int R = st.order_of_key({r+1, (int)0}); int L = st.order_of_key({l, (int)0}); // cerr << "L: " << L << " R: " << R << '\n'; last = R - L ; }else{ last = get(l, r, k); } cout << last << '\n'; } } }; /* 5 0 1 1 5 1 1 4 1 1 3 3 1 5 1 3 1 3 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...