oj.uz

Submission #268519

# Submission time Handle Problem Language Result Execution time Memory
268519 2020-08-16T12:31:33 Z stefantaga Queue (CEOI06_queue) C++14
0 / 100
 1000 ms 2680 KB 
#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]={v[i].y,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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 18 ms 384 KB Output isn't correct
4 Incorrect 16 ms 544 KB Output isn't correct
5 Incorrect 31 ms 1792 KB Output isn't correct
6 Incorrect 219 ms 2424 KB Output isn't correct
7 Incorrect 985 ms 2680 KB Output isn't correct
8 Execution timed out 1079 ms 1912 KB Time limit exceeded
9 Execution timed out 1085 ms 1996 KB Time limit exceeded
10 Execution timed out 1027 ms 1760 KB Time limit exceeded
11 Execution timed out 1057 ms 1912 KB Time limit exceeded
12 Execution timed out 1043 ms 1720 KB Time limit exceeded
13 Execution timed out 1094 ms 1800 KB Time limit exceeded
14 Execution timed out 1067 ms 2040 KB Time limit exceeded
15 Execution timed out 1070 ms 1812 KB Time limit exceeded
16 Execution timed out 1064 ms 1912 KB Time limit exceeded
17 Execution timed out 1099 ms 760 KB Time limit exceeded
18 Execution timed out 1087 ms 1016 KB Time limit exceeded
19 Execution timed out 1077 ms 1048 KB Time limit exceeded
20 Execution timed out 1045 ms 1528 KB Time limit exceeded
21 Execution timed out 1029 ms 2036 KB Time limit exceeded
22 Execution timed out 1065 ms 2048 KB Time limit exceeded
23 Execution timed out 1048 ms 1912 KB Time limit exceeded
24 Execution timed out 1035 ms 2040 KB Time limit exceeded
25 Execution timed out 1093 ms 1956 KB Time limit exceeded