31552023-02-20 23:02:40AncsaZsonglőrködéscpp11Time limit exceeded 35/1001.6s6924 KiB
#include <bits/stdc++.h>

using namespace std;
typedef struct{
    int e;
    int v;
    //bool volte=false;
} Interv;

/*
5
1 5
4 5
5 8
5 9
1 9
*/

/*
9
1 3
2 4
8 10
1 7
2 7
2 3
9 11
3 9
3 8
*/
bool eszerint(Interv i1, Interv i2)
{
    if (i1.e!=i2.e)
       return i1.e<i2.e;
    else
       return i1.v<i2.v;
}

void qkiir(queue<Interv> q)
{
    queue<Interv> seged=q;
    Interv v;
    cout<<endl;
    while(!seged.empty())
    {
        v=seged.front();
        cout<<v.e<<".."<<v.v<<" ";
        seged.pop();
    }
    cout<<endl;
}


int main()
{
    int n;
    cin>>n;
    vector<Interv> musor(n);

    for(int i=0;i<n;i++)
    {
        cin>>musor.at(i).e>>musor.at(i).v;
    }
/*
    for(Interv x: musor)
        cout<<x.e<<"-"<<x.v<<" ";
*/
    //cout<<endl;


    sort(musor.begin(),musor.end(),eszerint);
    /*
    for(Interv x: musor)
        cout<<x.e<<"-"<<x.v<<endl;
*/

    queue <Interv> sor;
    Interv jelol;
    jelol.e=-1;
    jelol.v=-1;

    for(Interv x: musor)
    {
        sor.push(x);
    }

    Interv most, uj;
    uj=jelol;
    sor.push(uj);
    int szamlal=0;
    while(sor.size()>1)
    {
        if (uj.e==-1)
        {
            most=sor.front();
            sor.pop();
            //cout<<endl<<most.e<<"--"<<most.v<<" ";
            szamlal++;
        }
        else
        {
            most=uj;
        }
        //qkiir(sor);

        uj=sor.front();
            //cout<<uj.e<<"**"<<uj.v<<" ";
        sor.pop();
        while(most.v>uj.e && uj.e!=-1)
        {
              sor.push(uj);
              uj=sor.front();
              sor.pop();
              //qkiir(sor);
        }

        if(most.v==uj.e)
            {
               //cout<<uj.e<<"--"<<uj.v<<" ";
               //most=uj;
               //most=uj;
               //sor.pop();
               //uj=sor.front();
               //qkiir(sor);
            }
        else if (most.v<uj.e )
          while(uj.e!=-1)
          {
                  sor.push(uj);
                  uj=sor.front();
                  sor.pop();
          }

        if(uj.e==-1)
        {
               sor.push(uj);
        }
    }
    cout << szamlal << endl;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1688 KiB
2Accepted3ms1848 KiB
subtask20/20
3Accepted12ms2088 KiB
4Time limit exceeded1.57s2628 KiB
5Time limit exceeded1.578s4212 KiB
6Time limit exceeded1.578s4780 KiB
7Time limit exceeded1.555s5096 KiB
8Time limit exceeded1.58s5400 KiB
9Time limit exceeded1.583s5408 KiB
10Time limit exceeded1.562s5488 KiB
11Time limit exceeded1.564s5476 KiB
subtask335/35
12Accepted3ms3148 KiB
13Accepted3ms3144 KiB
14Accepted3ms3120 KiB
15Accepted3ms3252 KiB
16Accepted4ms3468 KiB
17Accepted4ms3572 KiB
18Accepted4ms3576 KiB
19Accepted4ms3788 KiB
20Accepted4ms4048 KiB
subtask40/45
21Accepted13ms4184 KiB
22Time limit exceeded1.6s4420 KiB
23Time limit exceeded1.536s5968 KiB
24Time limit exceeded1.552s6488 KiB
25Time limit exceeded1.531s6876 KiB
26Time limit exceeded1.564s6872 KiB
27Time limit exceeded1.565s6924 KiB
28Time limit exceeded1.56s6804 KiB
29Time limit exceeded1.585s6920 KiB