Zero Game

input/code.cpp: In function 'int main()':
input/code.cpp:97:6: warning: unused variable 'zerosLeft' [-Wunused-variable]
  int zerosLeft = 0;
      ^

#include <bits/stdc++.h>
using namespace std;
int ok[1010101];
const int N = 1<<20;
int st[2*N];
vector<int> mx[20];
int so[N];
int qu[N];
int sumOnes(int a, int b) {
	if(b < 0) return 0;
	if(b < a) {
		return 0;
	}
	return so[b+1] - so[a];
}
int sumZeros(int a, int b) {
	if(b < 0) return 0;
	if(b < a) return 0;
	return b-a+1 - (sumOnes(a, b));
}
int getMax(int a, int b) {
	if(a == b) return a;
	int q = log(b-a+1)/log(2);
	int sz = 1<<q;
//	cout<<a<<' '<<b<<' '<<q<<' '<<sz<<' '<<mx[q][a]<<' '<<mx[q][b-sz+1]<<endl;
	return max(mx[q][a], mx[q][b-sz+1]);
}
int ans[N];

int main() {
	for(int i = 0; i < 20; ++i) mx[i].resize(N);
	string s;
	cin>>s;
	int q;
	cin>>q;
	for(int i = 0; i < q; ++i) {
		cin>>qu[i];
	}
	int n = s.size();
	for(int i = 0; i < n; ++i) s[i] -= '0';
	for(int i = 0; i < n; ++i) {
		so[i+1] = so[i] + s[i];
	}
	if(sumZeros(0, n-1) == 0) {
		for(int j = 0; j < q ;++j) cout<<0<<'\n';
		return 0;
	}
	ok[n] = n;
	for(int i = n-1; i >= 0; --i) {
		int sum = 0;
		ok[i] = n;

		for(int j = i; j < n;) {
			if(s[j] == 0) sum++;
			else sum--;
			if(sum >= 0) {
				ok[i] = j;
				break;
			}
			//eli nyt sum < 0
			if(ok[j+1] != j+1){
				j = ok[j+1]+1;
			}
			else ++j;
		}
	}
	/*
	for(int i = 0; i < n; ++i) {
		cout<<i<<' '<<ok[i]<<'\n';
	}
	cout<<'\n';
	*/
	for(int i = 0; i < n; ++i) {
		mx[0][i] = i;
	}
		int siz = 1;
	for(int i = 1; i < 20; ++i) {
		for(int j = 0; j < n; ++j) {
			int q = mx[i-1][j];
			int w = mx[i-1][j+siz];

			if(ok[q] > ok[w]) {
				mx[i][j] = q;
			}
			else mx[i][j] = w;
			//if(j < 10) cout<<q<<' '<<w<<' '<<mx[i][j]<<"        ";
			//if(j < 10) cout<<mx[i][j]<<' ';
		}
		siz *= 2;
		//cout<<'\n';
	}
	//cout<<getMax(0, 5)<<' '<<getMax(7, 10)<<endl;
	//getMax(0, 5);
	//getMax(7, 10);
	int qpos[N] = {0};
	int qused[N] = {0};
	int zerosLeft = 0;
	//for(int i = 0; i < n; ++i) if(s[i] == 0) ++zerosLeft;
	for(int i = 0; i < q; ++i) qused[i] = (s[0] == 1);
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < q; ++j) {
			while(qpos[j] < n-1) {
				if(s[qpos[j]+1] == 0) ++qpos[j];
				else if(qused[j] < qu[j]) {
					++qused[j];
					++qpos[j];
				}
				else break;
			}
			/*
			if(j == 0) {
				cout<<i<<' '<<qpos[j]<<' ';
			}
			*/
			//cout<<j<<' '<<qpos[j]<<' '<<qused[j]<<' '<<n<<' '<<qu[j]<<endl;
			int z = getMax(i, qpos[j]); //koordinaatti
			/*
			if(j == 0) {
				cout<<z<<' '<<ok[z]<<'\n';
			}
			*/
			if(ok[z] > qpos[j]) {
				int score = sumZeros(i, z-1) + min(sumZeros(z, n-1), qu[j] - sumOnes(i, z-1));
			//	if(j == 0) cout<<sumZeros(i, z-1)<<' '<<sumZeros(z, n-1)<<'\n';
				ans[j] = max(score, ans[j]);
			}
			else {
				ans[j] = max(ans[j], sumZeros(i, qpos[j]));
			}
			if(s[i] == 1) {
				--qused[j];
			}
		}
	}
	for(int i = 0; i < q; ++i) {
		cout<<ans[i]<<'\n';
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: RUNTIME ERROR

Test 5

Verdict: RUNTIME ERROR

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: RUNTIME ERROR

Test 8

Verdict: RUNTIME ERROR

Test 9

Verdict: RUNTIME ERROR

Test 10

Verdict: RUNTIME ERROR

Test 11

Verdict: RUNTIME ERROR

Test 12

Verdict: RUNTIME ERROR

Test 13

Verdict: RUNTIME ERROR

Test 14

Verdict: RUNTIME ERROR

Test 15

Verdict: RUNTIME ERROR

Test 16

Verdict: RUNTIME ERROR

Test 17

Verdict: RUNTIME ERROR

Test 18

Verdict: RUNTIME ERROR

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER