Submission #468907

#TimeUsernameProblemLanguageResultExecution timeMemory
468907JovanBSegments (IZhO18_segments)C++17
59 / 100
943 ms28400 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const ll N = 200000; const ll K = 400; const ll INF = 2000000005; ll L[N+5], R[N+5]; ll mxl[N+5]; ll mnl[N+5]; ll gde[N+5]; vector <tuple <ll, ll, ll>> rs[N+5]; vector <tuple <ll, ll, ll>> sz[N+5]; vector <tuple <ll, ll, ll>> vec[N+5]; ll n; ll query1(ll r, ll val){ ll res = 0; for(ll i=1; i<=n/K+2; i++){ if(rs[i].empty() || mnl[i] > r) continue; if(mxl[i] <= r){ auto c = rs[i].end() - lower_bound(rs[i].begin(), rs[i].end(), make_tuple(val, 0, 0)); res += c; } else{ for(auto pr : rs[i]) if(get<0>(pr) >= val && get<1>(pr) <= r) res++; } } return res; } ll query2(ll l, ll r, ll val){ if(r < l) return 0; ll res = 0; for(ll i=1; i<=n/K+2; i++){ if(sz[i].empty() || mnl[i] > r || mxl[i] < l) continue; if(l <= mnl[i] && mxl[i] <= r){ auto c = sz[i].end() - lower_bound(sz[i].begin(), sz[i].end(), make_tuple(val, 0, 0)); res += c; } else{ for(auto pr : sz[i]) if(l <= get<1>(pr) && get<1>(pr) <= r && get<0>(pr) >= val) res++; } } return res; } void Rebuild(){ vector <ll> vc; for(ll i=1; i<=n/K+2; i++){ for(auto c : vec[i]) vc.push_back(get<2>(c)); sz[i].clear(); rs[i].clear(); vec[i].clear(); mnl[i] = INF; mxl[i] = 0; } ll tjm = 1; for(auto i : vc){ if(vec[tjm].size() > K) tjm++; vec[tjm].push_back({L[i], R[i], i}); rs[tjm].push_back({R[i], L[i], i}); sz[tjm].push_back({R[i] - L[i] + 1, L[i], i}); mnl[tjm] = min(mnl[tjm], L[i]); mxl[tjm] = max(mxl[tjm], L[i]); gde[i] = tjm; } for(ll i=1; i<=tjm; i++){ sort(rs[i].begin(), rs[i].end()); sort(sz[i].begin(), sz[i].end()); } } void ubaci(vector <tuple <ll, ll, ll>> &vc, tuple <ll, ll, ll> x){ for(ll i=0; i<vc.size(); i++){ if(vc[i] > x){ vc.insert(vc.begin() + i, x); return; } } vc.push_back(x); } void izbaci(vector <tuple <ll, ll, ll>> &vc, ll x){ for(ll i=0; i<vc.size(); i++){ if(get<2>(vc[i]) == x){ vc.erase(vc.begin() + i); return; } } } int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; ll T; cin >> n >> T; ll res = 0; ll tjm = 0; ll act = 0; for(ll qry=1; qry<=n; qry++){ ll typ; cin >> typ; if(typ == 1){ act++; ll l, r; cin >> l >> r; l = (l ^ (T*res)); r = (r ^ (T*res)); ++tjm; L[tjm] = l; R[tjm] = r; gde[tjm] = 1; for(ll i=1; i<=n/K+2; i++){ if(vec[i].size() == 0) continue; gde[tjm] = i; if(mxl[i] > L[tjm]) break; } ubaci(vec[gde[tjm]], {(ll)L[tjm], R[tjm], tjm}); ubaci(rs[gde[tjm]], {(ll)R[tjm], L[tjm], tjm}); ubaci(sz[gde[tjm]], {R[tjm] - L[tjm] + 1, L[tjm], tjm}); mxl[gde[tjm]] = max(mxl[gde[tjm]], L[tjm]); mnl[gde[tjm]] = min(mnl[gde[tjm]], L[tjm]); if(vec[gde[tjm]].size() > 2*K) Rebuild(); } else if(typ == 2){ act--; ll id; cin >> id; izbaci(vec[gde[id]], id); izbaci(rs[gde[id]], id); izbaci(sz[gde[id]], id); } else{ ll l, r, k; cin >> l >> r >> k; l = (l ^ (T*res)); r = (r ^ (T*res)); if(l > r) swap(l, r); res = 0; if(k == 0) res = act; else{ if(r - l + 1 >= k) res += query1(l - 1, l + k - 1); res += query2(l, r - k + 1, k); } cout << res << "\n"; } } return 0; }

Compilation message (stderr)

segments.cpp: In function 'void ubaci(std::vector<std::tuple<long long int, long long int, long long int> >&, std::tuple<long long int, long long int, long long int>)':
segments.cpp:80:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(ll i=0; i<vc.size(); i++){
      |                 ~^~~~~~~~~~
segments.cpp: In function 'void izbaci(std::vector<std::tuple<long long int, long long int, long long int> >&, ll)':
segments.cpp:90:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll i=0; i<vc.size(); i++){
      |                 ~^~~~~~~~~~
#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...