| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 154602 |
2019-09-23T08:49:02 Z |
stefdasca |
Ruka (COI15_ruka) |
C++14 |
|
1566 ms |
524288 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n, q, oooo;
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][270000];
vector<vector<int> >aint2[2][270000];
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());
}
int nec(int st, int dr)
{
int ans = 0;
while(st < dr)
{
int mid = (st + dr) / 2;
ans = ans * 2 + 1;
st = mid + 1;
}
return ans;
}
void build(int nod, int st, int dr)
{
for(int i = 0; i <= 1; ++i)
{
aint[i][nod].clear();
aint2[i][nod].clear();
if(oooo == 0)
aint2[i][nod].resize(3 * (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 <= 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);
oooo = 1;
}
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;
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;
}
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)
{
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;
}
sool += query2(0, nod, 0, 0, aint[0][nod].size() - 1, ans, aint[0][nod].size() - 1, mx);
}
}
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;
}
sool += query2(1, nod, 0, 0, aint[1][nod].size() - 1, ans, aint[1][nod].size() - 1, my);
}
}
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;
}
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:102:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int oo = 0; oo < aint[i][nod].size(); ++oo)
~~~^~~~~~~~~~~~~~~~~~~~~
ruka.cpp:116:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int qu = 0; qu < aint[i][nod << 1].size(); ++qu)
~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:118: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:125: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:246: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:283:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mod.size() >= buk)
~~~~~~~~~~~^~~~~~
ruka.cpp:297:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mod.size() >= buk)
~~~~~~~~~~~^~~~~~
ruka.cpp:314:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mod.size() >= buk)
~~~~~~~~~~~^~~~~~
ruka.cpp:268:9: warning: unused variable 'ans' [-Wunused-variable]
int ans = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25720 KB |
Output is correct |
| 2 |
Correct |
26 ms |
25720 KB |
Output is correct |
| 3 |
Correct |
27 ms |
25720 KB |
Output is correct |
| 4 |
Correct |
28 ms |
25752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25720 KB |
Output is correct |
| 2 |
Correct |
26 ms |
25720 KB |
Output is correct |
| 3 |
Correct |
27 ms |
25720 KB |
Output is correct |
| 4 |
Correct |
28 ms |
25752 KB |
Output is correct |
| 5 |
Runtime error |
1566 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
25720 KB |
Output is correct |
| 2 |
Correct |
26 ms |
25720 KB |
Output is correct |
| 3 |
Correct |
27 ms |
25720 KB |
Output is correct |
| 4 |
Correct |
28 ms |
25752 KB |
Output is correct |
| 5 |
Runtime error |
1566 ms |
524288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
