| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 636713 |
2022-08-30T00:32:50 Z |
abeker |
Ruka (COI15_ruka) |
C++17 |
|
442 ms |
44936 KB |
#include <bits/stdc++.h>
using namespace std;
vector <int> operator +(vector <int> a, vector <int> b) {
int len = a.size();
assert(b.size() == len);
vector <int> c(len);
for (int i = 0; i < len; i++)
c[i] = a[i] + b[i];
return c;
}
class Fenwick {
vector <int> fen;
vector <int> values;
vector <pair <int, int>> toDo;
public:
void update(int x, int val, bool silent = true) {
if (!val)
return;
if (silent) {
toDo.push_back({x, val});
return;
}
for (x++; x < fen.size(); x += x & -x)
fen[x] += val;
}
int get(int x, bool silent = true) {
if (silent) {
toDo.push_back({x, 0});
return 0;
}
int res = 0;
for (x++; x; x -= x & -x)
res += fen[x];
return res;
}
int compress(int x) {
return lower_bound(values.begin(), values.end(), x) - values.begin();
}
vector <int> run() {
for (auto it : toDo)
values.push_back(it.first);
sort(values.begin(), values.end());
values.resize(unique(values.begin(), values.end()) - values.begin());
fen.resize(values.size() + 1);
vector <int> res;
for (auto it : toDo)
if (it.second)
update(compress(it.first), it.second, false);
else
res.push_back(get(compress(it.first), false));
return res;
}
};
class Counter {
int n;
int cursor, shift;
vector <int> seq, pref, maks;
Fenwick Left, Right;
public:
Counter(int _n, int st) {
n = _n;
seq.resize(n + 1);
pref.resize(n + 1);
maks.resize(n + 1);
seq[0] = st;
cursor = 1;
shift = 0;
}
Counter(){}
void build() {
pref[0] = maks[0] = seq[0];
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + seq[i];
maks[i] = max(pref[i], pref[i - 1]);
Right.update(maks[i], 1);
}
}
void set(int pos, int val) {
assert(!(val % 2));
seq[pos] = val;
}
void change(int val) {
shift += val - seq[cursor];
set(cursor, val);
Right.update(maks[cursor], -1);
maks[cursor] = max(pref[cursor - 1] - shift, pref[cursor]);
Right.update(maks[cursor], 1);
}
void backward() {
if (cursor == 1)
return;
cursor--;
Left.update(maks[cursor], -1);
maks[cursor] -= shift;
pref[cursor] -= shift;
Right.update(maks[cursor], 1);
}
void forward() {
if (cursor == n)
return;
Right.update(maks[cursor], -1);
maks[cursor] += shift;
pref[cursor] += shift;
Left.update(maks[cursor], 1);
cursor++;
}
void add_query() {
Left.get(0);
Right.get(-shift);
}
vector <int> get_queries() {
return Left.run() + Right.run();
}
};
int N;
Counter C[4];
void load() {
scanf("%d", &N);
for (int j = 0; j < 4; j++)
C[j] = Counter(N, j % 2 ? -1 : 1);
for (int i = 1; i <= N; i++) {
int x, y;
scanf("%d%d", &x, &y);
for (int j = 0; j < 4; j++)
C[j].set(i, vector <int>{x, -x, y, -y}[j]);
}
}
void solve() {
int M;
scanf("%d", &M);
for (int j = 0; j < 4; j++)
C[j].build();
while (M--) {
char cmd;
scanf(" %c", &cmd);
if (cmd == 'C') {
int nx, ny;
scanf("%d%d", &nx, &ny);
for (int j = 0; j < 4; j++)
C[j].change(vector <int>{nx, -nx, ny, -ny}[j]);
}
else if (cmd == 'B')
for (int j = 0; j < 4; j++)
C[j].backward();
else if (cmd == 'F')
for (int j = 0; j < 4; j++)
C[j].forward();
else
for (int j = 0; j < 4; j++)
C[j].add_query();
}
vector <int> ans = C[0].get_queries();
for (int j = 1; j < 4; j++)
ans = ans + C[j].get_queries();
for (auto it : ans)
printf("%d\n", 2 * N - it);
}
int main() {
double timer = clock();
load();
solve();
fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC);
return 0;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from ruka.cpp:1:
ruka.cpp: In function 'std::vector<int> operator+(std::vector<int>, std::vector<int>)':
ruka.cpp:6:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
6 | assert(b.size() == len);
| ~~~~~~~~~^~~~~~
ruka.cpp: In member function 'void Fenwick::update(int, int, bool)':
ruka.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (x++; x < fen.size(); x += x & -x)
| ~~^~~~~~~~~~~~
ruka.cpp: In function 'void load()':
ruka.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
ruka.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
ruka.cpp: In function 'void solve()':
ruka.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | scanf("%d", &M);
| ~~~~~^~~~~~~~~~
ruka.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | scanf(" %c", &cmd);
| ~~~~~^~~~~~~~~~~~~
ruka.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | scanf("%d%d", &nx, &ny);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
580 KB |
Output is correct |
| 4 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
580 KB |
Output is correct |
| 4 |
Correct |
2 ms |
468 KB |
Output is correct |
| 5 |
Correct |
148 ms |
17660 KB |
Output is correct |
| 6 |
Correct |
131 ms |
14300 KB |
Output is correct |
| 7 |
Correct |
147 ms |
17548 KB |
Output is correct |
| 8 |
Correct |
145 ms |
17824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
580 KB |
Output is correct |
| 4 |
Correct |
2 ms |
468 KB |
Output is correct |
| 5 |
Correct |
148 ms |
17660 KB |
Output is correct |
| 6 |
Correct |
131 ms |
14300 KB |
Output is correct |
| 7 |
Correct |
147 ms |
17548 KB |
Output is correct |
| 8 |
Correct |
145 ms |
17824 KB |
Output is correct |
| 9 |
Correct |
399 ms |
40164 KB |
Output is correct |
| 10 |
Correct |
442 ms |
44936 KB |
Output is correct |
| 11 |
Correct |
399 ms |
40948 KB |
Output is correct |
| 12 |
Correct |
402 ms |
40880 KB |
Output is correct |
