792D - Paths in a Complete Binary Tree - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define int long long
//#define endl '\n'

int n;

pair<int,char> getlevel(int u){
    int lvl = 1;
    int v = n/2;
    char last;
    while(v != u){
        if (v > u) v -= n/(1ll<<(++lvl)), last = 'L';
        else v += n/(1ll<<(++lvl)), last = 'R';
    }
    return {lvl,last};
}

signed main() {
    cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(0);
    int q;cin>>n>>q;
    ++n;
    int mx = log2(n);
    while(q--){
        int u;cin>>u;
        string s;cin>>s;
        auto [lvl,pos] = getlevel(u);
        for(auto &x:s){
            if (x == 'U'){
                if (lvl > 1)
                    u += (n/(1ll<<(lvl))) * (pos == 'L' ? 1 : -1);
            }
            if (x == 'L'){
                if (lvl < mx)
                    u -= (n/(1ll<<(lvl+1)));
            }
            if (x == 'R'){
                if (lvl < mx)
                    u += (n/(1ll<<(lvl+1)));
            }
            lvl = getlevel(u).first;
            pos = getlevel(u).second;
        }
        cout<<u<<endl;
    }
    return 0;
}