Submission #268576

#	Time	Username	Problem	Language	Result	Execution time	Memory
268576		stefantaga	Queue (CEOI06_queue)	C++14	0 / 100	733 ms	5348 KiB

queue

#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;
}
void insereaza (int val1)
{
    int st=1,dr=q1,mij,sol=0,i;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (valori[val1]>=mij)
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    q1++;
    for (i=q1;i>sol+1;i--)
    {
        valori[i]=valori[i-1];
    }
    valori[sol+1]=val1;
}
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);
        insereaza(pozitie1);
        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;
}

• Subtask 1: 0 / 100