제출 #667292

#제출 시각아이디문제언어결과실행 시간메모리
667292Kaztaev_AlisherSegments (IZhO18_segments)C++17
0 / 100
5069 ms6724 KiB
//#pragma GCC optomize ("Ofast") //#pragma GCC optomize ("unroll-loops") //#pragma GCC target ("avx,avx2,fma") #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define sz size #define cl clear #define ins insert #define ers erase #define pii pair < int , int > #define pll pair< long long , long long > #define all(x) x.begin() , x.end() #define ios 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 tostr(x) to_string(x) #define tonum(s) atoi(s.c_str()) #define seon(x) setprecision(x) #define bpop(x) __builtin_popcount(x) #define deb(x) cerr << #x << " = " << x << endl; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; const double PI = 3.14159265; const ll N = 1e5+5; const ll mod = 1e9+7; const ll inf = 1e9; const ll INF = 1e18; using namespace std; int n , t , BL , bsz; vector<pair<int , pii>> v; vector<int> bl[N] , br[N]; int mn[N] = {inf}; int mx[N] , pr[N]; void build(){ BL = 400; sort(all(v)); for(int i = 0 ; i < v.sz(); i++){ int j = i / BL; bl[j].pb(v[i].S.S); br[j].pb(v[i].S.F); mn[j] = min(mn[j] , v[i].F); mx[j] = max(mx[j] , v[i].F); pr[j]++; } bsz = (v.sz()-1)/BL; for(int j = 0 ; j <= bsz; j++) if(j) pr[j] += pr[j-1]; for(int i = 0; i <= bsz; i++){ sort(all(bl[i])); sort(all(br[i])); } } int get(int l , int r , int k){ int ans = v.sz(); for(int i = 0; i <= bsz; i++){ if(mn[i] < k && mx[i] >= k){ int pref = 0; if(i) pref = pr[i-1]; for(int j = pref; j < pr[i]; j++){ if(v[j].F < k){ ans--; continue; } int L = v[j].S.F , R = v[j].S.S; if(L > r-k+1 || R < l+k-1) ans--; } } else if(mn[i] >= k){ int res = br[i].sz(); for(int L = 0 , R = br[i].sz()-1; L <= R;){ int md = (L+R) >> 1; if(br[i][md] > r-k+1) res = md , R = md-1; else L = md+1; } ans -= br[i].sz()-res; res = -1; for(int L = 0 , R = bl[i].sz()-1; L <= R;){ int md = (L+R) >> 1; if(bl[i][md] < l+k-1) res = md , L = md+1; else R = md-1; } ans -= res+1; } else ans -= br[i].sz(); } return ans; } void solve(){ cin >> n >> t; int lst = 0 , ok = 0; while(n--){ int tp , l , r; cin >> tp >> l >> r; l = (l ^ (t * lst)); r = (r ^ (t * lst)); if(l > r) swap(l , r); if(tp == 3){ if(ok == 0) build(); ok = 1; int k; cin >> k; lst = get(l,r,k); cout << lst <<"\n"; } else v.pb({r-l+1 , {l , r}}); } } signed main(){ ios; solve(); return 0; } /* 6 0 1 3 10 1 6 10 1 3 5 3 11 33 22 3 4 6 2 3 7 10 3 */

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In function 'void build()':
segments.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0 ; i < v.sz(); 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...