QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #593663 | #6836. A Plus B Problem | 333zhan | WA | 0ms | 3604kb | C++20 | 7.0kb | 2024-09-27 15:24:37 | 2024-09-27 15:24:37 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
template<class Info, class Tag>
struct SegmentTree {
vector <Info> tr;
vector <Tag> tag;
int n;
SegmentTree (int n_) : tr (n_ * 4 + 10), tag (n_ * 4 + 10) {
n = n_;
}
SegmentTree (int n_, vector <Info> info) {
n = n_;
tr.resize (n * 4 + 10);
tag.resize (n * 4 + 10);
auto build = [&] (auto &&self, int rt, int l, int r) -> void {
tr[rt].l = l;
tr[rt].r = r;
if (l == r) {
tr[rt] = info[l];
return;
}
int mid = (l + r) / 2;
self (self, lson, l, mid);
self (self, rson, mid + 1, r);
pushup (rt);
};
build (build, 1, 0, n);
}
void pushup (int rt) {
tr[rt] = tr[lson] + tr[rson];
}
void apply (int rt, const Tag &x) {
tr[rt].apply (x);
tag[rt].apply (x);
}
void pushdown (int rt) {
apply (lson, tag[rt]);
apply (rson, tag[rt]);
tag[rt] = Tag ();
}
void modify (int rt, int l, int r, int x, int y, const Tag &t) {
if (l > y || r < x) {
return;
}
if (l >= x && r <= y) {
apply (rt, t);
return;
}
pushdown (rt);
int mid = (l + r) / 2;
modify (lson, l, mid, x, y, t);
modify (rson, mid + 1, r, x, y, t);
pushup (rt);
}
Info query (int rt, int l, int r, int x, int y) {
if (l >= x && r <= y) {
return tr[rt];
}
pushdown (rt);
int mid = (l + r) / 2;
if (x <= mid && y > mid) {
return query (lson, l, mid, x, y) + query (rson, mid + 1, r, x, y);
} else if (x <= mid) {
return query (lson, l, mid, x, y);
} else {
return query (rson, mid + 1, r, x, y);
}
}
template <class F>
int findFirst (int rt, int l, int r, int x, int y, F &&pred) {
if (l > y || r < x) {
return -1;
}
if (l >= x && r <= y && ! pred (tr[rt])) {
return -1;
}
if (l == r) {
return l;
}
pushdown (rt);
int mid = (l + r) / 2;
int ans = findFirst (lson, l, mid, x, y, pred);
if (ans == -1) {
ans = findFirst (rson, mid + 1, r, x, y, pred);
}
return ans;
}
template <class F>
int findLast (int rt, int l, int r, int x, int y, F &&pred) {
if (l > y || r < x) {
return -1;
}
if (l >= x && r <= y && ! pred (tr[rt])) {
return -1;
}
if (l == r) {
return l;
}
pushdown (rt);
int mid = (l + r) / 2;
int ans = findLast (rson, mid + 1, r, x, y, pred);
if (ans == -1) {
ans = findLast (lson, l, mid, x, y, pred);
}
return ans;
}
};
struct Tag {
int lazy = 10;
void apply (const Tag &x) & {
if (x.lazy != 10) {
lazy = x.lazy;
}
}
};
struct Info {
int l, r;
int ans = 0;
int len = 0;
void apply (const Tag &x) & {
if (x.lazy != 10) {
ans = x.lazy * len;
}
}
};
Info operator+(const Info &x, const Info &y) {
Info c;
c.ans = x.ans + y.ans;
c.len = x.len + y.len;
return c;
}
void solve () {
int n, q;
cin >> n >> q;
string A, B;
cin >> A >> B;
A = " " + A;
B = " " + B;
vector a (2, vector <int> (n + 2));
for (int i = 1; i <= n; i ++) {
a[0][i] = A[i] - '0';
a[1][i] = B[i] - '0';
}
vector <Info> info (n + 1);
for (int i = n; i >= 1; i --) {
info[i].ans = info[i].ans + (A[i] - '0') + (B[i] - '0');
info[i - 1].ans += info[i].ans / 10;
info[i].ans %= 10;
info[i].len = 1;
}
info[0].len = 1;
SegmentTree <Info, Tag> seg (n, info);
while (q --) {
int r, c, d;
cin >> r >> c >> d;
r --;
// cerr << r << " " << c << " " << d << '\n';
int ans1 = 0, ans2 = 0;
if (a[r][c] == d) {
ans1 = seg.query (1, 0, n, c, c).ans;
} else if (a[r][c] < d) {
int t = seg.query (1, 0, n, c, c).ans;
int e = d - a[r][c];
if (t + e >= 10) {
int x = -1;
if (c > 1) {
x = seg.findFirst (1, 0, n, 1, c - 1,
[&] (const Info &info) {
return info.ans == (c - info.l) * 9;
}
);
}
ans2 = 1;
if (x != -1) {
seg.modify (1, 0, n, x, c - 1, {0});
ans2 += c - x;
} else {
x = c;
}
if (x != 1) {
ans2 ++;
}
int f = seg.query (1, 0, n, x - 1, x - 1).ans;
seg.modify (1, 0, n, x - 1, x - 1, {f + 1});
seg.modify (1, 0, n, c, c, {(t + e) % 10});
ans1 = (t + e) % 10;
} else {
ans1 = t + e;
ans2 = 2;
seg.modify (1, 0, n, c, c, {t + e});
}
} else {
int t = seg.query (1, 0, n, c, c).ans;
int e = a[r][c] - d;
if (t - e < 0) {
int x = seg.findFirst (1, 0, n, 0, c - 1,
[&](const Info &info) {
return info.ans == 0;
}
);
// if (c == 3) {
// cerr << x << '\n';
// }
ans2 = 3;
if (x != -1) {
seg.modify (1, 0, n, x, c - 1, {9});
ans2 += c - x;
} else {
x = c;
}
int f = seg.query (1, 0, n, x - 1, x - 1).ans;
// if (c == 3) {
// cerr << f << '\n';
// }
seg.modify (1, 0, n, x - 1, x - 1, {f - 1});
seg.modify (1, 0, n, c, c, {(t - e + 10) % 10});
ans1 = (t - e + 10) % 10;
// if (c == 3) {
// cerr << t << " " << e << '\n';
// }
} else {
ans1 = t - e;
ans2 = 2;
seg.modify (1, 0, n, c, c, {t + e});
}
}
a[r][c] = d;
cout << ans1 << " " << ans2 << '\n';
}
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
int T = 1;
// cin >> T;
while (T --) {
solve ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
5 5 01234 56789 2 1 0 2 2 1 2 3 2 2 4 3 2 5 4
output:
0 2 3 2 5 3 7 3 8 3
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3604kb
input:
1 1 1 1 1 1 9
output:
0 1
result:
wrong answer 1st lines differ - expected: '0 2', found: '0 1'