So I think that my solution to this problem: Problem - D - Codeforces runs in O(qn) time, which should run under 2 seconds, but it seems to not work. What is going wrong?
#include <bits/stdc++.h>
using namespace::std;
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define FMOD 998244353
#define MOD 1000000007
int n;
const int MAXN = 1<<18;
int a[MAXN] = {0};
int solve(string s, int g, int level) {
int left = 2*g; // 0 means left
int right = 2*g+1; // 1 means right
if (s[g-1]=='1') {
if (level==n-1) {
a[g-1]=1;
return 1;
}
else {
a[g-1]=solve(s, left, level+1);
solve(s, right, level+1);
}
} else if (s[g-1]=='0') {
if (level==n-1) {
a[g-1]=1;
return 1;
}
else {
a[g-1]=solve(s, right, level+1);
solve(s, left, level+1);
}
} else {
if (level==n-1) {
a[g-1]=2;
return 2;
}
else {
a[g-1]=solve(s, left, level+1)+solve(s, right, level+1);
}
}
return a[g-1];
}
int main() {
fastio;
cin >> n;
int x = 1<<n;
string s; cin >> s;
reverse(s.begin(), s.end());
solve(s, 1, 0);
int q; cin >> q;
F0R(i, q) {
int c; char t; cin >> c >> t;
s[x-1-c]=t;
c = x-c;
if (2*c>=x) {
if (t=='?') a[c-1]=2;
else a[c-1]=1;
c/=2;
}
do {
if (s[c-1]=='?') a[c-1]=a[2*c-1]+a[2*c];
else if (s[c-1]=='1') a[c-1]=a[2*c-1];
else a[c-1]=a[2*c];
c=c/2;
} while (c>0);
// if (s[c-1]=='?') a[c-1]=a[2*c-1]+a[2*c];
// else if (s[c-1]=='1') a[c-1]=a[2*c-1];
// else a[c-1]=a[2*c];
cout << a[0] << "\n";
// F0R(i, x) {
// cout << a[i] << " ";
// }
// cout << "\n";
// cout << s << "\n";
// cout << "\n\n\n\n";
}
}