QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593755 | #6836. A Plus B Problem | 333zhan | WA | 255ms | 3872kb | C++20 | 6.9kb | 2024-09-27 15:52:17 | 2024-09-27 15:52:17 |
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 {
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 ans = 0;
int minn = 10;
int maxx = -1;
void apply (const Tag &x) & {
if (x.lazy != 10) {
ans = minn = maxx = x.lazy;
}
}
};
Info operator+(const Info &x, const Info &y) {
Info c;
c.minn = min (x.minn, y.minn);
c.maxx = max (x.maxx, y.maxx);
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].maxx = info[i].minn = info[i].ans;
}
info[0].maxx = info[0].minn = info[0].ans;
SegmentTree <Info, Tag> seg (n, info);
while (q --) {
int r, c, d;
cin >> r >> c >> d;
r --;
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.minn == 9;
}
);
}
ans2 = 2;
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 = -1;
if (c > 1) {
x = seg.findFirst (1, 0, n, 1, c - 1,
[&](const Info &info) {
return info.maxx == 0;
}
);
}
ans2 = 3;
// if (c == 4) {
// cerr << x << '\n';
// }
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;
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;
} 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;
}
/*
0869373820
3130626142
0869376820
3130626142
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 1 1 1 1 1 9
output:
0 2
result:
ok single line: '0 2'
Test #3:
score: -100
Wrong Answer
time: 255ms
memory: 3820kb
input:
10 1000000 6869373857 3130626142 1 9 2 1 10 0 2 7 6 1 1 0 1 7 6 2 10 4 2 3 9 2 4 2 2 4 4 2 7 0 1 2 4 1 9 8 1 3 7 1 7 1 1 1 5 2 1 6 1 3 5 2 5 8 2 6 5 1 6 3 1 3 8 2 4 2 2 6 3 2 2 6 1 10 9 2 1 1 2 5 4 1 1 8 2 4 0 1 9 1 1 1 8 2 4 2 2 9 2 1 10 3 1 8 9 1 4 6 2 3 0 1 1 6 1 7 1 1 10 9 2 4 4 2 5 9 2 1 8 1 9 ...
output:
6 2 2 2 9 0 3 2 2 8 8 3 6 2 2 2 4 2 6 8 5 2 9 9 1 2 5 4 0 2 3 2 9 3 1 2 2 3 8 3 2 3 8 3 6 2 9 3 7 11 0 2 6 6 7 2 7 2 3 6 7 0 3 5 1 2 1 2 0 5 0 2 1 4 5 2 0 0 9 11 2 2 5 2 7 2 5 2 2 2 0 2 4 2 1 3 1 2 1 0 5 2 4 2 2 2 4 2 4 2 1 2 5 2 3 3 6 3 0 2 1 2 9 2 1 2 2 2 3 0 2 2 8 11 6 2 2 2 2 7 7 2 9 4 1 8 0 0 9...
result:
wrong answer 6th lines differ - expected: '4 2', found: '8 3'