# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
268565 | stefantaga | Queue (CEOI06_queue) | C++14 | 1098 ms | 2236 KiB |
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;
map <int,int> m;
map <int,pair<int,int> > m1;
int nr,i,n,q;
struct wow
{
int x,y;
}v[50005];
struct query
{
int poz;char tip;
}query[50005];
int q1,valori[50005];
int pozitie (int x)
{
int st,dr,mij,sol=0;
if (m1.find(x)!=m1.end())
{
sol=m1[x].second;
st=m1[x].second+1;
dr=q1;
while (st<=dr)
{
mij=(st+dr)/2;
if (m1[x].first>=mij)
{
sol=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
m1[x].first+=sol-m1[x].second;
return m1[x].first;
}
st=1;
dr=q1;
while (st<=dr)
{
mij=(st+dr)/2;
if (valori[mij]<=x)
{
sol=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
return x+sol;
}
int pozitie1;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("queue.in");
ofstream cout("queue.out");
#endif // HOME
cin>>n;
for (i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y;
pozitie1=pozitie(v[i].y);
valori[++q1]=pozitie1;
sort (valori+1,valori+q1+1);
m1[v[i].x]={pozitie1,i};
m[v[i].x]=1;
m[v[i].y]=1;
}
cin>>q;
for (i=1;i<=q;i++)
{
cin>>query[i].tip>>query[i].poz;
if (query[i].tip=='P')
{
cout<<pozitie(query[i].poz)<<'\n';
}
else
{
cout<<"1"<<'\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |