This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
vector<lg> o;
for(int i = 1; i <= n; i++)
{
cin >> l[i] >> r[i];
o.push_back(l[i]);
o.push_back(r[i]);
}
sort(o.begin(), o.end());
for(int i = 0; i < o.size(); i++)
{
int it = o[i];
if(i && it == o[i-1]) continue;
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)
| ~~~^~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < o.size(); i++)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |