Help: What is the Time Complexity of this? 
Разница между en1 и en2, 163 символ(ов) изменены
I was attempting the E problem of round #878 Div 3. I am getting TLE in my code but it seems to me that the Time complexity of the code if _O(T * (t + q))_ which should get accepted. Please tell me the mistake in the code. ↵

**Approach**: I am storing the position which are unblocked at time (relative to current time) in a queue. The string a and b are just a copy of s1 and s2 which will be blocked and unblocked throughout the process (s1 and s2 are not altered). ↵

Problem: [Div 3 E](https://codeforces.me/contest/1840/problem/E)  ↵
My submission: [Submission](https://codeforces.me/contest/1840/submission/208859532)↵



<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵
#define rep(i, n) for (long long i = 0; i < n; ++i)↵
#define coutyes cout << "YES" << nl↵
#define coutno cout << "NO" << nl↵
#define IOS                       \↵
    ios_base::sync_with_stdio(0); \↵
    cin.tie(0);                   \↵
    cout.tie(0)↵
#define nl '\n'↵
using namespace std;↵
using ll = long long;↵
 ↵
void solve()↵
{↵
    string a, b, s1, s2; cin >> s1 >> s2;↵
    a = s1, b = s2;↵
    ll t, q; cin >> t >> q;↵
    queue<ll> qu;↵
    rep(i,t) qu.push(-1);↵
    while(q--){↵
        ll x; cin >> x;↵

        if(qu.front()==-1) qu.pop();↵
        else{↵
            ll k=qu.front();↵
            a[k]=s1[k], b[k]=s2[k];↵
            qu.pop();↵
        }↵

        if(x==3){↵
            qu.push(-1);↵
            if(a==b)coutyes;↵
            else coutno;↵
        }↵
        else if(x==2){↵
            qu.push(-1);↵
            ll p, q, r, s; cin >> p >> q >> r >> s;↵
            if(p==1 && r==1)↵
                swap(a[q - 1], a[s - 1]), swap(s1[q - 1], s1[s - 1]);↵
            else if(p==1 && r==2)↵
                swap(a[q - 1], b[s - 1]), swap(s1[q - 1], s2[s - 1]);↵
            else if(p==2 && r==1)↵
                swap(b[q - 1], a[s - 1]), swap(s2[q - 1], s1[s - 1]);↵
            else↵
                swap(b[q - 1], b[s - 1]), swap(s2[q - 1], s2[s - 1]);↵
        }↵
        else{↵
            ll y; cin>>y;↵
            qu.push(y - 1); a[y-1]='A'; b[y-1]='A';↵
        }↵
    }       ↵
}↵
signed main()↵
{↵
    IOS;↵
    int t=1; cin >> t;↵
    while(t--) solve();↵
}↵
~~~~~↵


</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский SP_22 2023-06-07 09:40:40 163 Tiny change: 'oblem/E)\nMy submi' -> 'oblem/E)\n\nMy submi'
en1 Английский SP_22 2023-06-07 09:37:22 2108 Initial revision (published)