This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Time: 15-07-2024 16:33:04
// Problem: E - Osumnjičeni
// Contest: Virtual Judge - COCI 2021 Contest # 2
// URL: https://vjudge.net/contest/640690#problem/E
// Memory Limit: 512 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;
bool valid(multiset<pair<int,int>> &se,pair<int,int> p)
{
auto it=se.insert(p);
if (it!=se.begin())
{
it--;
if ((*it).second>=p.first)
{
se.erase(++it);
return 0;
}
it++;
}
it++;
if (it!=se.end())
{
if ((*it).first<=p.second)
{
se.erase(--it);
return 0;
}
}
return 1;
}
int main()
{
int n;
cin>>n;
vector<pair<int,int>> vec;
for (int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
vec.push_back({l,r});
}
multiset<pair<int,int>> se;
int i=0,j=0;
int rc[n+1][18];
while (i<n)
{
if (j<n)
{
while (j<n && valid(se,vec[j]))
j++;
}
rc[i][0]=j;
se.erase(se.find(vec[i]));
i++;
}
for (int i=0;i<18;i++)
rc[n][i]=n;
for (int p=1;p<18;p++)
for (int i=0;i<n;i++)
rc[i][p]=rc[rc[i][p-1]][p-1];
int q;
cin>>q;
while (q--)
{
int a,b;
cin>>a>>b;
a--,b--;
int ans=1;
for (int p=17;p>=0;p--)
if (rc[a][p]<=b)
ans+=(1<<p),a=rc[a][p];
cout<<ans<<'\n';
}
return 0;
}
# | 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... |