Aiuto per Reserved Seats(seats)

Aiuto
1

buongiorno, stavo cercando di risolvere reserved seats, tuttavia gli ultimi due test case vanno in TLE. suppongo che il problema sia quando devono salire i passeggeri in quanto devo cercare il primo posto libero. ho già provato a tenere traccia del primo posto libero in modo da evitare il for per la ricerca ma senza successo. questo è il codice:

#include <bits/stdc++.h>
using namespace std;

void sposta(int,vector<int>&,vector<int>&);

int ans=0;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int N,Q,n;
char ch;
cin>>N>>Q;
vector<int>K(N,-1);
vector<int>K2(N,-1);
    for(int i=0;i<Q;i++)
    {
        cin>>ch>>n;
        if(ch=='b')
        {
            for(int j=0;j<N;j++)
            {
                if(K[j]==-1){
                    K[j]=n;
                    K2[n]=j;
                    break;
                }
                else if(j==n)
                {
                    ++ans;
                    int temp=K[j];
                    K[j]=n;
                    K2[n]=j;
                    sposta(temp,K,K2);
                    break;
                }
            }
        }
        else if(ch=='l')
        {
            K[K2[n]]=-1;
        }
    }
    cout<<ans;
    return 0;
}
void sposta(int n,vector<int>&K,vector<int>&K2)
{
while(1){    
    if(K[n]==-1){
        K[n]=n;
        K2[n]=n;
        break;
    }
    else
    {
        ++ans;
        int temp=K[n];
        K[n]=n;
        K2[n]=n;
        n=temp;
    }
}
}

consigli?

2

Utilizzando, ad esempio, la struttura set di STL hai sempre il primo posto libero del treno invece di usare il ciclo for() che ti porta ad avere una complessità che va in TLE.
Inserendo, inizialmente, tutti i posti liberi del treno nel set, se un posto viene occupato si elimina dal set e se si libera viene inserito nel set.
Con questa ottimizzazione il tuo codice prende 100/100.

3

grazie per il consiglio, dopo provo a implementarlo

4

l’ho appena implementato ed effettivamente il set era la scelta giusta. grazie mille