Submission #637448

#TimeUsernameProblemLanguageResultExecution timeMemory
637448Sam_a17Segments (IZhO18_segments)C++14
7 / 100
135 ms13024 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define blt __builtin_popcount #define pb push_back #define popf pop_front #define popb pop_back void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(long double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; long long intersect(pair<long long, long long> a, pair<long long, long long> b) { a.first = max(a.first, b.first); a.second = min(a.second, b.second); return a.second - a.first + 1; } const int N = 200005, inf = 1e9; pair<int, int> id[N]; void solve_() { long long n, t; cin >> n >> t; if(n <= 5000) { set<long long> mex; for(int i = 1; i <= N; i++) { mex.insert(i); } vector<pair<long long, long long>> par(N + 10); set<pair<long long, pair<long long, long long>>> st; long long lst = 0; while(n--) { int type; cin >> type; if(type == 1) { long long it = *mex.begin(); long long a, b; cin >> a >> b; long long li = a ^ (t * lst), ri = b ^ (t * lst); st.insert({it, {li, ri}}); par[it] = {li, ri}; mex.erase(mex.begin()); } else if(type == 2) { long long id; cin >> id; st.erase(st.find({id, par[id]})); } else { long long a, b, k; cin >> a >> b >> k; long long li = a ^ (t * lst), ri = b ^ (t * lst); if(li > ri) { swap(li, ri); } long long answ = 0; pair<long long, long long> p = {li, ri}; for(auto i: st) { if(intersect(p, i.second) >= k) { ++answ; } } lst = answ; cout << answ << endl; } } return; } set<long long> mex; for(int i = 1; i <= n; i++) { mex.insert(i); } Tree<pair<int, int>> rx, lx; int cnt = 0, last_ans = 0; while(n--) { int t; cin >> t; if(t == 1) { auto it = *mex.begin(); mex.erase(mex.begin()); int l, r; cin >> l >> r; l = l ^ (t * last_ans); r = r ^ (t * last_ans); if(l > r) { swap(l, r); } id[it] = {l, r}; cnt++; // rx.insert({r, it}); lx.insert({l, it}); } else if(t == 2) { int ind; cin >> ind; int l = id[ind].first, r = id[ind].second; mex.insert(ind), cnt--; rx.erase({r, ind}); lx.erase({l, ind}); } else { // 2ic poqr r // 1,0 0 // 2,0 1 // 3,0 2 // 4,0 3 int l, r, k; cin >> l >> r >> k; l = l ^ (t * last_ans); r = r ^ (t * last_ans); if(l > r) { swap(l, r); } int countL = rx.order_of_key({l - 1, inf}); int countR = sz(lx) - lx.order_of_key({r + 1, -1}); cout << cnt - (countL + countR) << "\n"; last_ans = cnt - (countL + countR); } } } int main() { setIO(); auto solve = [&](int test_case)-> void { while(test_case--) { solve_(); } }; int test_cases = 1; solve(test_cases); return 0; }

Compilation message (stderr)

segments.cpp: In function 'void setIO(std::string)':
segments.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...