제출 #154954

#제출 시각아이디문제언어결과실행 시간메모리
154954andrewSegments (IZhO18_segments)C++17
0 / 100
279 ms7844 KiB
#include <bits/stdc++.h> #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define p_b push_back #define pll pair<ll,ll> #define pii pair<int,int> #define m_p make_pair #define all(x) x.begin(),x.end() #define sset ordered_set #define sqr(x) (x)*(x) #define pw(x) (1ll << x) using namespace std; typedef long long ll; typedef long double ld; const ll MAXN = 1123456; const ll N = 2e5; const ll inf = 3e18; int buben = 1000; mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count()); template <typename T> void vout(T s){cout << s << endl;exit(0);} pii a[N + 3]; int stn; int WD[N + 3]; int Wstn; pii b[N + 3]; int Stn; bool f_deleted[N + 3], will_deleted[N + 3]; int luk, ruk; ll Len_Block, Len; vector <ll> V[501], V1[501]; void build(int Nt){ Len_Block = 1; Len = Nt; while(sqr(Len_Block) < Len)Len_Block++; for(int i = 0; i <= Len / Len_Block; i++){ V[i].clear(); V1[i].clear(); } for(int i = 0; i < Len; i++){ V[i / Len_Block].p_b(a[i + 1].fi); V1[i / Len_Block].p_b(a[i + 1].se - a[i + 1].fi + 1); } for(int i = 0; i <= (Len - 1) / Len_Block; i++){ sort(all(V[i])); sort(all(V1[i])); } } int Val; int V_more(int l, int r){ l--, r--; int ans = 0; for(int i = l; i <= r;){ if(i % Len_Block == 0 && i + Len_Block - 1 <= r){ ans += V[i].size() - (lower_bound(all(V[i]), Val) - V[i].begin()); i += Len_Block; }else{ if(a[i + 1].fi >= Val)ans++; i++; } } return ans; } int V1_more(int l, int r){ l--, r--; int ans = 0; for(int i = l; i <= r;){ if(i % Len_Block == 0 && i + Len_Block - 1 <= r){ ans += V1[i].size() - (lower_bound(all(V1[i]), Val) - V1[i].begin()); i += Len_Block; }else{ if(a[i + 1].se - a[i + 1].fi + 1 >= Val)ans++; i++; } } return ans; } struct qry{ short t; int a, b, c, Id; }; qry c[N + 3]; int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int n, t; cin >> n >> t; for(int i = 1; i <= n; i++){ cin >> c[i].t; if(c[i].t == 1){ cin >> c[i].a >> c[i].b; }else if(c[i].t == 2){ cin >> c[i].a; }else{ cin >> c[i].a >> c[i].b >> c[i].c; } } int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j; for(i = 1; i <= n; i++){ if(i % buben == 0){ Wstn = 0; for(j = i; j <= min(n, i + buben - 1); j++){ if(c[j].t == 2){ will_deleted[c[j].a] = 1; if(c[j].a <= Stn){ Wstn++; WD[Wstn] = c[j].a; } } } stn = 0; for(j = 1; j <= Stn; j++)if(!will_deleted[j]){ stn++; a[stn] = b[j]; } if(stn){ sort(a + 1, a + stn + 1); build(stn); } l = i; } if(c[i].t == 1){ c[i].a ^= t * last_ans; c[i].b ^= t * last_ans; if(c[i].a > c[i].b)swap(c[i].a, c[i].b); Stn++; c[i].Id = Stn; b[Stn] = {c[i].a, c[i].b}; }else if(c[i].t == 2){ f_deleted[c[i].a] = 1; will_deleted[c[i].a] = 1; }else if(c[i].t == 3){ c[i].a ^= t * last_ans; c[i].b ^= t * last_ans; if(c[i].a > c[i].b)swap(c[i].a, c[i].b); if(c[i].b - c[i].a + 1 < c[i].c){ cout << "0\n"; last_ans = 0; continue; } ans = 0; k = c[i].c; for(j = l; j < i; j++)if(c[j].t == 1 && !f_deleted[c[j].Id]){ if(min(c[i].b, c[j].b) - max(c[i].a, c[j].a) + 1 >= c[i].c || c[i].c == 0)ans++; } for(j = 1; j <= Wstn; j++)if(!f_deleted[WD[j]]){ if(min(c[i].b, b[WD[j]].se) - max(c[i].a, b[WD[j]].fi) + 1 >= c[i].c || c[i].c == 0)ans++; } if(!k)ans += stn; else{ if(stn){ L = 1, R = stn; while(L < R){ mid = (L + R) >> 1; if(a[mid].fi < c[i].a)L = mid + 1; else R = mid; } if(a[L].fi < c[i].a)L++; if(L != 1){ Val = k + c[i].a - 1; ans += V_more(1, L - 1); } Le = L; L = 1, R = stn; while(L < R){ mid = (L + R) >> 1; if(a[mid].fi <= c[i].b - k + 1)L = mid + 1; else R = mid; } if(a[L].fi <= c[i].b - k + 1)L++; if(Le < L){ Val = k; ans += V1_more(Le, L - 1); } } } cout << ans << "\n"; last_ans = ans; } } return 0; }

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

segments.cpp: In function 'int main()':
segments.cpp:123:43: warning: unused variable 'Ri' [-Wunused-variable]
     int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
                                           ^~
segments.cpp:123:47: warning: unused variable 'L1' [-Wunused-variable]
     int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
                                               ^~
segments.cpp:123:51: warning: unused variable 'R1' [-Wunused-variable]
     int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
                                                   ^~
#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...