WA 15
Posted by
moji 26 Jul 2013 15:51
any idea's?
using a simple segment tree:
//In the name of God
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q, srt[N], a[N], m, t[N], rep[N];
char c[N];
void update(int n, int b, int e, int x) {
if (b == e) {
t[n] = (rep[b]? srt[b]: 0);
return;
}
int l = n << 1, r = l | 1, m = b + e >> 1;
if (x <= m)
update(l, b, m, x);
else
update(r, m + 1, e, x);
t[n] = __gcd(t[l], t[r]);
}
int main() {
ios_base::sync_with_stdio(false);
cin >> q;
for (int i = 0; i < q; i++) {
cin >> c[i] >> a[i];
srt[i] = a[i];
}
sort(srt, srt + q);
m = unique(srt, srt + q) - srt;
for (int i = 0; i < q; i++) {
int tmp = std::lower_bound(srt, srt + m, a[i]) - srt;
rep[tmp] += 44 - c[i];
if (!!(rep[tmp] - 44 + c[i]) != !!(rep[tmp]))
update(1, 0, m - 1, tmp);
cout << (t[1]? t[1]: 1) << '\n';
}
return 0;
}