Submission #862686

#TimeUsernameProblemLanguageResultExecution timeMemory
862686Cyber_WolfOsumnjičeni (COCI21_osumnjiceni)C++17
110 / 110
925 ms95064 KiB
#include <bits/stdc++.h> using namespace std; #define lg long long #define mid (lr+hr)/2 const lg N = 2e5+5; lg l[N], r[N], anc[N][20], n, seg[(N << 3)][2]; void doLazy(lg node, lg lr, lg hr) { if(!seg[node][1]) return; seg[node][0] += seg[node][1]*(hr-lr+1); if(lr != hr) { for(int ch = node*2; ch <= node*2+1; ch++) { seg[ch][1] += seg[node][1]; } } seg[node][1] = 0; } void upd(lg node, lg lr, lg hr, lg lq, lg hq, lg val) { doLazy(node, lr, hr); if(lr > hq || lq > hr) return; if(lq <= lr & hr <= hq) { seg[node][1] += val; doLazy(node, lr, hr); return; } upd(node << 1, lr, mid, lq, hq, val); upd(node << 1 | 1, mid+1, hr, lq, hq, val); seg[node][0] = seg[node << 1][0]+seg[node << 1 | 1][0]; return; } lg get(lg node, lg lr, lg hr, lg lq, lg hq) { doLazy(node, lr, hr); if(lr > hq || lq > hr) return 0; if(lq <= lr && hr <= hq) return seg[node][0]; return (get(node << 1, lr, mid, lq, hq)+get(node << 1 | 1, mid+1, hr, lq, hq)); } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); lg n; cin >> n; unordered_map<lg, lg> mp; lg id = 1; set<lg> o; for(int i = 1; i <= n; i++) { cin >> l[i] >> r[i]; o.insert(l[i]); o.insert(r[i]); } for(auto it : o) { mp[it] = id++; } for(int i = 1; i <= n; i++) { l[i] = mp[l[i]]; r[i] = mp[r[i]]; } lg en = 1; for(int i = 1; i <= n; i++) { while(en <= n) { if(get(1, 1, 4e5, l[en], r[en])) { break; } upd(1, 1, 4e5, l[en], r[en], 1); en++; } anc[i][0] = en-1; upd(1, 1, 4e5, l[i], r[i], -1); } for(int i = n; i >= 1; i--) { for(int j = 1; j < 19; j++) { anc[i][j] = anc[anc[i][j-1]+1][j-1]; } } lg q; cin >> q; while(q--) { lg a, b; cin >> a >> b; lg ans = 0; for(int i = 18; i >= 0 && a <= b; i--) { if(anc[a][i] <= b && anc[a][i]) { ans += (1ll << i); a = anc[a][i]+1; } } if(a <= b) ans++; cout << ans << '\n'; } }

Compilation message (stderr)

Main.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:30:8: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   30 |  if(lq <= lr & hr <= hq)
      |     ~~~^~~~~
#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...