32652023-02-23 15:55:23rennRészekre (40)cpp17Time limit exceeded 18/40575ms6608 KiB
#include <bits/stdc++.h>
using namespace std;

#define GOTTAGOFAST cin.tie(0); ios::sync_with_stdio(0);

struct Node {
    int value;
    Node *next;
    Node *prev;
};

int main()
{
    GOTTAGOFAST

    int n;
    cin >> n;

    vector<Node> pontok(n+2);

    pontok[0].value = 1000001;
    pontok[0].next = &pontok[1];
    pontok[n+1].prev = &pontok[n];

    for(int i = 1; i <= n; i++)
    {
        cin >> pontok[i].value;
        pontok[i].prev = &pontok[i-1];
        pontok[i].next = &pontok[i+1];
    }

    int tval = pontok[n].value, inters = 0;
    bool cutt = false;
    Node *max = &pontok[n];
    Node *curr = max;
    Node *temp;

    while(true)
    {
        inters++;
        cutt = true;
        temp = max->prev;
        curr = max;

        max->prev->next = max->next;
        max->next->prev = max->prev;
        while(temp != &pontok[0])
        {
            if(cutt && temp->value >= curr->value)
            {
                max = temp;
                cutt = false;
            }

            if(temp->value < curr->value)
            {
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
                curr = temp;
            }
            temp = temp->prev;
        }
        if(cutt) break;
    }

    cout << inters << "\n";

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base18/40
1Accepted0/03ms1868 KiB
2Accepted0/0122ms6608 KiB
3Accepted2/23ms2316 KiB
4Accepted2/23ms2524 KiB
5Accepted2/23ms2752 KiB
6Accepted3/33ms2980 KiB
7Accepted3/36ms3268 KiB
8Accepted3/312ms3452 KiB
9Accepted3/341ms3704 KiB
10Time limit exceeded0/3561ms4096 KiB
11Time limit exceeded0/3574ms4552 KiB
12Time limit exceeded0/3546ms5512 KiB
13Time limit exceeded0/4570ms5228 KiB
14Time limit exceeded0/4564ms5408 KiB
15Time limit exceeded0/5575ms5596 KiB