#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n, q;
pair<int, int> dir[100002];
char tip;
int poz = 1, a, b;
int lstque = -1;
void brut()
{
int ans = 0;
for(int i = 1; i <= q; ++i)
{
cin >> tip;
if(tip == 'B')
poz = max(1, poz - 1);
if(tip == 'F')
poz = min(poz + 1, n);
if(tip == 'C')
{
cin >> a >> b;
lstque = -1;
dir[poz] = {a, b};
}
if(tip == 'Q')
{
if(lstque == -1)
{
ans = 0;
int pa = 1, pb = 1;
for(int j = 1; j <= n; ++j)
{
if(pa > 0 && pa + dir[j].fi < 0)
++ans;
if(pa < 0 && pa + dir[j].fi > 0)
++ans;
if(pb > 0 && pb + dir[j].se < 0)
++ans;
if(pb < 0 && pb + dir[j].se > 0)
++ans;
pa += dir[j].fi;
pb += dir[j].se;
}
lstque = i;
}
cout << ans << '\n';
}
}
}
bool is[100002];
deque<int>mod;
int counter = 0;
int prefixx[100002], prefixy[100002];
int ans[100002];
/// 0/1 = x/y, 0/1 = increasing/decreasing, nod
vector<pair<int, int> >aint[2][400002];
vector<vector<int> >aint2[2][400002];
//ofstream out("ruka.out");
void build2(int B, int R, int nod, int st, int dr)
{
if(nod != 0)
{
vector<int>ro;
for(int i = st; i <= dr; ++i)
ro.push_back(aint2[B][R][0][i]);
aint2[B][R][nod] = ro;
}
if(st == dr)
return;
int mid = (st + dr) / 2;
build2(B, R, nod * 2 + 1, st, mid);
build2(B, R, nod * 2 + 2, mid+1, dr);
sort(aint2[B][R][nod].begin(), aint2[B][R][nod].end());
}
void build(int nod, int st, int dr)
{
for(int i = 0; i <= 1; ++i)
{
aint[i][nod].clear();
aint2[i][nod].clear();
aint2[i][nod].resize(4 * (dr - st + 1));
}
if(st == dr)
{
aint[0][nod].push_back({max(prefixx[st], prefixx[st - 1]), min(prefixx[st], prefixx[st - 1])});
aint[1][nod].push_back({max(prefixy[st], prefixy[st - 1]), min(prefixy[st], prefixy[st - 1])});
for(int i = 0; i <= 1; ++i)
{
vector<int>na;
for(int oo = 0; oo < aint[i][nod].size(); ++oo)
na.push_back(aint[i][nod][oo].se);
if(!na.size())
continue;
aint2[i][nod][0] = na;
build2(i, nod, 0, 0, na.size() - 1);
}
return;
}
int mid = (st + dr) / 2;
build(nod << 1, st, mid);
build(nod << 1|1, mid+1, dr);
for(int i = 0; i <= 1; ++i)
{
for(int qu = 0; qu < aint[i][nod << 1].size(); ++qu)
aint[i][nod].push_back(aint[i][nod << 1][qu]);
for(int qu = 0; qu < aint[i][nod << 1|1].size(); ++qu)
aint[i][nod].push_back(aint[i][nod << 1|1][qu]);
sort(aint[i][nod].begin(), aint[i][nod].end());
}
for(int i = 0; i <= 1; ++i)
{
vector<int>na;
for(int oo = 0; oo < aint[i][nod].size(); ++oo)
na.push_back(aint[i][nod][oo].se);
if(!na.size())
continue;
aint2[i][nod][0] = na;
build2(i, nod, 0, 0, na.size() - 1);
}
}
void rebuild(int start_poz)
{
memset(is, 0, sizeof(is));
mod.clear();
is[start_poz] = 1;
mod.push_back(start_poz);
prefixx[0] = 1;
prefixy[0] = 1;
for(int i = 1; i <= 4 * n; ++i)
{
aint[0][i].clear();
aint[1][i].clear();
aint2[0][i].clear();
aint2[1][i].clear();
}
for(int i = 1; i <= n; ++i)
{
ans[i] = ans[i-1];
if(prefixx[i-1] > 0 && prefixx[i-1] + dir[i].fi < 0)
++ans[i];
if(prefixx[i-1] < 0 && prefixx[i-1] + dir[i].fi > 0)
++ans[i];
if(prefixy[i-1] > 0 && prefixy[i-1] + dir[i].se < 0)
++ans[i];
if(prefixy[i-1] < 0 && prefixy[i-1] + dir[i].se > 0)
++ans[i];
prefixx[i] = prefixx[i-1] + dir[i].fi;
prefixy[i] = prefixy[i-1] + dir[i].se;
}
if(poz != n)
build(1, poz + 1, n);
}
int query2(int Bi, int Ro, int nod, int L, int R, int st, int dr, int threshold)
{
if(!aint2[Bi][Ro][nod].size())
return 0;
if(R < st || L > dr)
return 0;
if(st <= L && R <= dr)
{
int sst = 0;
int ddr = aint2[Bi][Ro][nod].size() - 1;
// out << Bi << " " << Fr << " " << Ro << " " << nod << " " << L << " " << R << " " << st << " " << dr << " " << threshold << '\n';
// for(int i = 0; i < aint2[Bi][Fr][Ro][nod].size(); ++i)
// out << aint2[Bi][Fr][Ro][nod][i] << " ";
// out << '\n';
if(aint2[Bi][Ro][nod][0] >= threshold)
return 0;
int ans = 0;
while(sst <= ddr)
{
int mid = (sst + ddr) / 2;
if(aint2[Bi][Ro][nod][mid] < threshold)
ans = mid, sst = mid + 1;
else
ddr = mid - 1;
}
// out << 0 << " " << ans << " " << (ans + 1) << '\n';
return (ans + 1);
}
int mid = (L + R) / 2;
int ro = query2(Bi, Ro, nod * 2 + 1, L, mid, st, dr, threshold);
int se = query2(Bi, Ro, nod * 2 + 2, mid + 1, R, st, dr, threshold);
return ro+se;
}
int query(int nod, int L, int R, int st, int dr, int mx, int my)
{
if(R < st || L > dr)
return 0;
if(st <= L && R <= dr)
{
// out << nod << " " << L << " " << R << " " << st << " " << dr << " " << mx << " " << my << '\n';
int sool = 0;
if(aint[0][nod].size())
{
int st = 0;
int dr = aint[0][nod].size() - 1;
int ans = 0;
if(aint[0][nod].back().fi >= mx)
{
while(st <= dr)
{
int mid = (st + dr) / 2;
if(aint[0][nod][mid].fi >= mx)
ans = mid, dr = mid - 1;
else
st = mid + 1;
}
// out << " a " << 0 << " " << 0 << " " << nod << " " << ans << '\n';
sool += query2(0, nod, 0, 0, aint[0][nod].size() - 1, ans, aint[0][nod].size() - 1, mx);
// out << sool << '\n';
}
}
if(aint[1][nod].size())
{
int st = 0;
int dr = aint[1][nod].size() - 1;
int ans = 0;
if(aint[1][nod].back().fi >= my)
{
while(st <= dr)
{
int mid = (st + dr) / 2;
if(aint[1][nod][mid].fi >= my)
ans = mid, dr = mid - 1;
else
st = mid + 1;
}
// out << " a " << 1 << " " << 0 << " " << nod << " " << ans << '\n';
sool += query2(1, nod, 0, 0, aint[1][nod].size() - 1, ans, aint[1][nod].size() - 1, my);
// out << sool << '\n';
}
}
return sool;
}
int mid = (L + R) / 2;
int ans1 = query(nod << 1, L, mid, st, dr, mx, my);
int ans2 = query(nod << 1|1, mid + 1, R, st, dr, mx, my);
return ans1 + ans2;
}
int solve(int start_poz)
{
int sol = 0;
int sumx = 0;
int sumy = 0;
int start = start_poz - 1;
sol = ans[start];
sumx = prefixx[start];
sumy = prefixy[start];
for(int i = 0; i < mod.size(); ++i)
{
if(sumx > 0 && sumx + dir[mod[i]].fi < 0)
++sol;
if(sumx < 0 && sumx + dir[mod[i]].fi > 0)
++sol;
if(sumy > 0 && sumy + dir[mod[i]].se < 0)
++sol;
if(sumy < 0 && sumy + dir[mod[i]].se > 0)
++sol;
start = mod[i];
sumx += dir[mod[i]].fi;
sumy += dir[mod[i]].se;
}
// out << "ince " << start_poz << " " << poz + 1 << " " << n << " " << sumx << " " << prefixx[mod.back()] << " " << sumy << " " << prefixy[mod.back()] << '\n';
if(mod.back() < n)
sol += query(1, start_poz + 1, n, mod.back() + 1, n, -(sumx - prefixx[mod.back()]), -(sumy - prefixy[mod.back()]));
return sol;
}
void solvegood()
{
int start_poz = 1;
rebuild(start_poz);
int ans = 0;
int buk = sqrt(q);
for(int i = 1; i <= q; ++i)
{
cin >> tip;
if(tip == 'B')
{
poz = max(1, poz - 1);
if(!is[poz])
{
is[poz] = 1;
if(mod.empty() || poz > mod.back())
mod.push_back(poz);
else
mod.push_front(poz);
if(mod.size() >= buk)
start_poz = poz, rebuild(start_poz);
}
}
if(tip == 'F')
{
poz = min(poz + 1, n);
if(!is[poz])
{
is[poz] = 1;
if(mod.empty() || poz > mod.back())
mod.push_back(poz);
else
mod.push_front(poz);
if(mod.size() >= buk)
start_poz = poz, rebuild(start_poz);
}
}
if(tip == 'Q')
cout << solve(start_poz) << '\n';
if(tip == 'C')
{
cin >> a >> b;
dir[poz] = {a, b};
if(!is[poz])
{
is[poz] = 1;
if(mod.empty() || poz > mod.back())
mod.push_back(poz);
else
mod.push_front(poz);
if(mod.size() >= buk)
start_poz = poz, rebuild(start_poz);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> dir[i].fi >> dir[i].se;
cin >> q;
if(1LL * n * q <= 300000000)
brut();
else
solvegood();
return 0;
}
Compilation message
ruka.cpp: In function 'void build(int, int, int)':
ruka.cpp:91:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int oo = 0; oo < aint[i][nod].size(); ++oo)
~~~^~~~~~~~~~~~~~~~~~~~~
ruka.cpp:105:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int qu = 0; qu < aint[i][nod << 1].size(); ++qu)
~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:107:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int qu = 0; qu < aint[i][nod << 1|1].size(); ++qu)
~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:114:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int oo = 0; oo < aint[i][nod].size(); ++oo)
~~~^~~~~~~~~~~~~~~~~~~~~
ruka.cpp: In function 'int solve(int)':
ruka.cpp:251:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < mod.size(); ++i)
~~^~~~~~~~~~~~
ruka.cpp: In function 'void solvegood()':
ruka.cpp:289:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mod.size() >= buk)
~~~~~~~~~~~^~~~~~
ruka.cpp:303:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mod.size() >= buk)
~~~~~~~~~~~^~~~~~
ruka.cpp:320:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mod.size() >= buk)
~~~~~~~~~~~^~~~~~
ruka.cpp:274:9: warning: unused variable 'ans' [-Wunused-variable]
int ans = 0;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 2 |
Correct |
38 ms |
37884 KB |
Output is correct |
| 3 |
Correct |
38 ms |
38040 KB |
Output is correct |
| 4 |
Correct |
40 ms |
37856 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 2 |
Correct |
38 ms |
37884 KB |
Output is correct |
| 3 |
Correct |
38 ms |
38040 KB |
Output is correct |
| 4 |
Correct |
40 ms |
37856 KB |
Output is correct |
| 5 |
Execution timed out |
2068 ms |
338004 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
37880 KB |
Output is correct |
| 2 |
Correct |
38 ms |
37884 KB |
Output is correct |
| 3 |
Correct |
38 ms |
38040 KB |
Output is correct |
| 4 |
Correct |
40 ms |
37856 KB |
Output is correct |
| 5 |
Execution timed out |
2068 ms |
338004 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
