이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
vector<pair<int, int> >aint[2][2][400002];
vector<vector<int> >aint2[2][2][400002];
void build2(int B, int F, int R, int nod, int st, int dr)
{
if(st == dr)
return;
int mid = (st + dr) / 2;
vector<int>ro, se;
for(int i = 0; i <= mid - st; ++i)
ro.push_back(aint2[B][F][R][nod][i]);
for(int i = mid - st + 1; i < aint2[B][F][R][nod].size(); ++i)
se.push_back(aint2[B][F][R][nod][i]);
aint2[B][F][R].push_back(ro);
aint2[B][F][R].push_back(se);
build2(B, F, R, nod, st, mid);
build2(B, F, R, nod, mid+1, dr);
sort(aint2[B][F][R][nod].begin(), aint2[B][F][R][nod].end());
}
void build(int nod, int st, int dr)
{
aint[0][0][nod].clear();
aint[0][1][nod].clear();
aint[1][0][nod].clear();
aint[1][1][nod].clear();
aint2[0][0][nod].clear();
aint2[0][1][nod].clear();
aint2[1][0][nod].clear();
aint2[1][1][nod].clear();
if(st == dr)
{
aint[0][(prefixx[st] < prefixx[st-1])][nod].push_back({prefixx[st], prefixx[st - 1]});
aint[1][(prefixy[st] < prefixy[st-1])][nod].push_back({prefixy[st], prefixy[st - 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 j = 0; j < aint[0][i][nod << 1].size(); ++j)
aint[0][i][nod].push_back(aint[0][i][nod << 1][j]);
for(int j = 0; j < aint[0][i][nod << 1|1].size(); ++j)
aint[0][i][nod].push_back(aint[0][i][nod << 1|1][j]);
for(int j = 0; j < aint[1][i][nod << 1].size(); ++j)
aint[1][i][nod].push_back(aint[1][i][nod << 1][j]);
for(int j = 0; j < aint[1][i][nod << 1|1].size(); ++j)
aint[1][i][nod].push_back(aint[1][i][nod << 1|1][j]);
sort(aint[0][i][nod].begin(), aint[0][i][nod].end());
sort(aint[1][i][nod].begin(), aint[1][i][nod].end());
}
for(int i = 0; i <= 1; ++i)
for(int j = 0; j <= 1; ++j)
{
vector<int>na;
for(int oo = 0; oo < na.size(); ++oo)
na.push_back(aint[i][j][nod][oo].se);
aint2[i][j][nod].push_back(na);
build2(i, j, nod, 0, 0, na.size() - 1);
}
}
void rebuild()
{
memset(is, 0, sizeof(is));
mod.clear();
prefixx[0] = 1;
prefixy[0] = 1;
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 Fr, int Ro, int nod, int L, int R, int st, int dr, int threshold)
{
if(R < st || L > dr)
return 0;
if(st <= L && R <= dr)
{
int st = 0;
int dr = aint2[Bi][Fr][Ro][nod].size() - 1;
if(Fr == 0)
{
if(aint2[Bi][Fr][Ro][nod][0] >= threshold)
return 0;
int ans = 0;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(aint2[Bi][Fr][Ro][nod][ans] < threshold)
ans = mid, st = mid + 1;
else
dr = mid - 1;
}
return ans;
}
else
{
if(aint2[Bi][Fr][Ro][nod].back() <= threshold)
return 0;
int ans = dr;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(aint2[Bi][Fr][Ro][nod][ans] >= threshold)
ans = mid, dr = mid - 1;
else
st = mid + 1;
}
return (aint2[Bi][Fr][Ro][nod].size() - ans);
}
}
int mid = (st + dr) / 2;
return query2(Bi, Fr, Ro, nod, L, mid, st, dr, threshold) + query2(Bi, Fr, Ro, nod, mid + 1, R, st, dr, threshold);
}
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)
{
int sool = 0;
for(int a = 0; a <= 1; ++a)
for(int b = 0; b <= 1; ++b)
{
if(!aint[a][b][nod].size())
continue;
int st = 0;
int dr = aint[a][b][nod].size() - 1;
int ans = dr * (b == 0);
if(ans == 0)
{
if(a == 0 && aint[a][b][nod][0].fi > mx)
continue;
if(a == 1 && aint[a][b][nod][0].fi > my)
continue;
}
if(ans == dr)
{
if(a == 0 && aint[a][b][nod].back().fi < mx)
continue;
if(a == 1 && aint[a][b][nod].back().fi < my)
continue;
}
while(st <= dr)
{
int mid = (st + dr) / 2;
if(b == 0)
{
if(a == 0)
{
if(aint[a][b][nod][mid].fi >= mx)
ans = mid, dr = mid - 1;
else
st = mid + 1;
}
else
{
if(aint[a][b][nod][mid].fi >= my)
ans = mid, dr = mid - 1;
else
st = mid + 1;
}
}
else
{
if(a == 0)
{
if(aint[a][b][nod][mid].fi <= mx)
ans = mid, st = mid + 1;
else
dr = mid - 1;
}
else
{
if(aint[a][b][nod][mid].fi <= my)
ans = mid, st = mid + 1;
else
dr = mid - 1;
}
}
}
if(b == 0)
{
if(a == 0)
sool += query2(a, b, nod, 0, 0, aint2[a][b][nod].size() - 1, ans, aint2[a][b][nod].size() - 1, mx);
else
sool += query2(a, b, nod, 0, 0, aint2[a][b][nod].size() - 1, ans, aint2[a][b][nod].size() - 1, my);
}
else
{
if(a == 0)
sool += query2(a, b, nod, 0, 0, aint2[a][b][nod].size() - 1, 0, ans, mx);
else
sool += query2(a, b, nod, 0, 0, aint2[a][b][nod].size() - 1, 0, ans, my);
}
}
return sool;
}
int mid = (st + dr) / 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 = 0;
if(!mod.size())
start = start_poz;
else
start = mod[0] - 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;
}
if(mod.empty())
{
if(poz < n)
sol += query(1, start_poz, n, poz + 1, n, -sumx, -sumy);
}
else
{
if(mod.back() < n)
sol += query(1, start_poz, n, mod.back() + 1, n, -sumx, -sumy);
}
return sol;
}
void solvegood()
{
int start_poz = 1;
rebuild();
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(tip == 'F')
poz = min(poz + 1, n);
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(is[poz] >= buk)
rebuild(), start_poz = 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;
}
컴파일 시 표준 에러 (stderr) 메시지
ruka.cpp: In function 'void build2(int, int, int, int, int, int)':
ruka.cpp:66:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = mid - st + 1; i < aint2[B][F][R][nod].size(); ++i)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp: In function 'void build(int, int, int)':
ruka.cpp:95:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < aint[0][i][nod << 1].size(); ++j)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:97:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < aint[0][i][nod << 1|1].size(); ++j)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:99:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < aint[1][i][nod << 1].size(); ++j)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:101:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < aint[1][i][nod << 1|1].size(); ++j)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:110:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int oo = 0; oo < na.size(); ++oo)
~~~^~~~~~~~~~~
ruka.cpp: In function 'int solve(int)':
ruka.cpp:283: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:313:9: warning: unused variable 'ans' [-Wunused-variable]
int ans = 0;
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |