Submission #268608

#	Time	Username	Problem	Language	Result	Execution time	Memory
268608		stefantaga	Queue (CEOI06_queue)	C++14	2 / 100	1098 ms	1732 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;
pair <int,int> valori[50005];
int pozitie (int x)
{
    int sol=0,i;
    if (m1.find(x)!=m1.end())
    {
        for (i=m1[x].second+1;i<=q1;i++)
        {
            if (valori[i].first<=valori[i].second)
            {
                if (valori[i].first<=m1[x].first+sol&&m1[x].first+sol<=valori[i].second)
            {
                sol++;
            }
            }
            else
            {
                 if (valori[i].first>=m1[x].first+sol&&m1[x].first+sol>=valori[i].second)
            {
                sol--;
            }
            }
        }
        m1[x].first+=sol;
        return m1[x].first;
    }
    for (i=1;i<=q1;i++)
        {
            if (valori[i].first<=valori[i].second)
            {
                if (valori[i].first<=x+sol&&x+sol<=valori[i].second)
            {
                sol++;
            }
            }
            else
            {
                if (valori[i].first>=x+sol&&x+sol>=valori[i].second)
            {
                sol--;
            }
            }
        }
    return x+sol;
}
int pozitie1,pozitie2;
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);
        pozitie2=pozitie(v[i].x);
        if (pozitie1<=pozitie2)
        {
            valori[++q1]={pozitie1,pozitie2-1};
            m1[v[i].x]={pozitie1,i};
        }
        else
        {
            valori[++q1]={pozitie1-1,pozitie2};
            m1[v[i].x]={pozitie1-1,i};
        }
    }
    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: 2 / 100