Submission #880419

#TimeUsernameProblemLanguageResultExecution timeMemory
880419mychecksedadRailway Trip 2 (JOI22_ho_t4)C++17
16 / 100
2063 ms110308 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 4e5+100, M = 1e5+10, K = 20; struct Data{ int L, R; }; int n, k, m, q, L[N][K], R[N][K], lazyL[N][K], lazyR[N][K]; Data up[N][K]; void build(int l, int r, int k, int bit){ lazyL[k][bit] = MOD; lazyR[k][bit] = 0; if(l == r){ L[k][bit] = l; R[k][bit] = l; return; } int mid = l+r>>1; build(l, mid, k<<1, bit); build(mid+1, r, k<<1|1, bit); L[k][bit] = min(L[k<<1][bit], L[k<<1|1][bit]); R[k][bit] = max(R[k<<1][bit], R[k<<1|1][bit]); } void pushL(int k, int bit){ L[k<<1][bit] = min(L[k<<1][bit], lazyL[k][bit]); L[k<<1|1][bit] = min(L[k<<1|1][bit], lazyL[k][bit]); lazyL[k<<1][bit] = min(lazyL[k<<1][bit], lazyL[k][bit]); lazyL[k<<1|1][bit] = min(lazyL[k<<1|1][bit], lazyL[k][bit]); lazyL[k][bit] = MOD; } void pushR(int k, int bit){ R[k<<1][bit] = max(R[k<<1][bit], lazyR[k][bit]); R[k<<1|1][bit] = max(R[k<<1|1][bit], lazyR[k][bit]); lazyR[k<<1][bit] = max(lazyR[k<<1][bit], lazyR[k][bit]); lazyR[k<<1|1][bit] = max(lazyR[k<<1|1][bit], lazyR[k][bit]); lazyR[k][bit] = 0; } void updateL(int l, int r, int ql, int qr, int k, int bit, int val){ if(ql > r || l > qr) return; if(ql <= l && r <= qr){ lazyL[k][bit] = min(lazyL[k][bit], val); L[k][bit] = min(L[k][bit], val); return; } pushL(k, bit); int mid = l+r>>1; updateL(l, mid, ql, qr, k<<1, bit, val); updateL(mid+1, r, ql, qr, k<<1|1, bit, val); L[k][bit] = min(L[k<<1][bit], L[k<<1|1][bit]); } void updateR(int l, int r, int ql, int qr, int k, int bit, int val){ if(ql > r || l > qr) return; if(ql <= l && r <= qr){ lazyR[k][bit] = max(lazyR[k][bit], val); R[k][bit] = max(R[k][bit], val); return; } pushR(k, bit); int mid = l+r>>1; updateR(l, mid, ql, qr, k<<1, bit, val); updateR(mid+1, r, ql, qr, k<<1|1, bit, val); R[k][bit] = max(R[k<<1][bit], R[k<<1|1][bit]); } void updateLL(int l, int r, int p, int k, int bit, int val){ if(l == r){ L[k][bit] = min(L[k][bit], val); return; } pushL(k, bit); int mid = l+r>>1; if(p <= mid) updateLL(l, mid, p, k<<1, bit, val); else updateLL(mid+1, r, p, k<<1|1, bit, val); L[k][bit] = min(L[k<<1][bit], L[k<<1|1][bit]); } void updateRR(int l, int r, int p, int k, int bit, int val){ if(l == r){ R[k][bit] = max(R[k][bit], val); return; } pushR(k, bit); int mid = l+r>>1; if(p <= mid) updateRR(l, mid, p, k<<1, bit, val); else updateRR(mid+1, r, p, k<<1|1, bit, val); R[k][bit] = max(R[k<<1][bit], R[k<<1|1][bit]); } int getL(int l, int r, int ql, int qr, int k, int bit){ if(ql > r || l > qr) return MOD; if(ql <= l && r <= qr) return L[k][bit]; int mid = l+r>>1; pushL(k, bit); return min(getL(l, mid, ql, qr, k<<1, bit), getL(mid+1, r, ql, qr, k<<1|1, bit)); } int getR(int l, int r, int ql, int qr, int k, int bit){ if(ql > r || l > qr) return 0; if(ql <= l && r <= qr) return R[k][bit]; int mid = l+r>>1; pushR(k, bit); return max(getR(l, mid, ql, qr, k<<1, bit), getR(mid+1, r, ql, qr, k<<1|1, bit)); } void solve(){ cin >> n >> k >> m; build(1, n, 1, 0); for(int i = 1; i <= m; ++i){ int l, r; cin >> l >> r; if(l < r){ int rk = min(r - 1, l + k - 1); updateR(1, n, l, rk, 1, 0, r); // cout << l << ' ' << rk << '\n'; }else{ int rk = max(r + 1, l - k + 1); updateL(1, n, rk, l, 1, 0, r); // cout << rk << ' ' << l << '\n'; } } for(int i = 1; i <= n; ++i) up[i][0] = {getL(1, n, i, i, 1, 0), getR(1, n, i, i, 1, 0)}; for(int j = 1; j < K; ++j){ build(1, n, 1, j); for(int i = 1; i <= n; ++i){ up[i][j] = {getL(1, n, up[i][j - 1].L, up[i][j - 1].R, 1, j - 1), getR(1, n, up[i][j - 1].L, up[i][j - 1].R, 1, j - 1)}; updateLL(1, n, i, 1, j, up[i][j].L); updateRR(1, n, i, 1, j, up[i][j].R); } } cin >> q; for(int i = 1; i <= q; ++i){ int l, r; cin >> l >> r; Data x = {l, l}; bool ok = 0; int ans = 0; for(int j = K - 1; j >= 0; --j){ Data u = {getL(1, n, x.L, x.R, 1, j), getR(1, n, x.L, x.R, 1, j)}; if(u.L <= r && u.R >= r){ ok = 1; }else{ x = u; ans += (1<<j); } // cout << x.L << ' ' << x.R << '\n'; } if(!ok) cout << "-1\n"; else{ cout << ans + 1 << '\n'; } } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int, int)':
Main.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void updateL(int, int, int, int, int, int, int)':
Main.cpp:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void updateR(int, int, int, int, int, int, int)':
Main.cpp:69:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void updateLL(int, int, int, int, int, int)':
Main.cpp:81:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'void updateRR(int, int, int, int, int, int)':
Main.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'int getL(int, int, int, int, int, int)':
Main.cpp:107:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'int getR(int, int, int, int, int, int)':
Main.cpp:114:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   int mid = l+r>>1;
      |             ~^~
Main.cpp: In function 'int main()':
Main.cpp:169:15: warning: unused variable 'aa' [-Wunused-variable]
  169 |   int tt = 1, aa;
      |               ^~
#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...