QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#593818#6836. A Plus B Problem333zhanWA 223ms3828kbC++206.8kb2024-09-27 16:13:012024-09-27 16:13:01

Judging History

你现在查看的是最新测评结果

  • [2024-09-27 16:13:01]
  • 评测
  • 测评结果：WA
  • 用时：223ms
  • 内存：3828kb
查看
  • [2024-09-27 16:13:01]
  • 提交

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;
                x = seg.findLast (1, 0, n, 0, c - 1, 
                    [&] (const Info &info) {
                        return info.minn < 9;
                    }
                );
                x ++;
                ans2 = 2;
                if (x != c) {
                    seg.modify (1, 0, n, x, c - 1, {0});
                    ans2 += c - x;
                }
                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;
                x = seg.findLast (1, 0, n, 0, c - 1, 
                    [&](const Info &info) {
                        return info.maxx > 0;
                    }
                );
                x ++;
                // if (c == 3) {
                //     cerr << seg.query (1, 0, n, 1, 2).maxx << '\n';
                //     cerr << x << '\n';
                // }
                ans2 = 3;
                if (x != c) {
                    seg.modify (1, 0, n, x, c - 1, {9});
                    ans2 += c - x;
                } 
                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;
} 
/*
0869376820
3130626142

0869376820
3130626144
*/
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3540kb

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: 3828kb

input:

1 1
1
1
1 1 9

output:

0 2

result:

ok single line: '0 2'

Test #3:

score: -100
Wrong Answer
time: 223ms
memory: 3572kb

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
4 2
6 2
2 2
4 2
6 5
6 3
2 4
7 2
2 2
8 2
1 2
5 2
1 3
2 3
8 3
8 2
2 2
6 2
1 3
3 3
7 3
7 3
0 2
9 3
6 4
0 0
1 3
4 2
7 3
0 3
8 3
8 3
8 3
2 0
3 3
0 3
2 3
5 2
9 2
4 2
8 2
3 3
5 3
3 2
5 0
4 2
3 2
1 2
4 2
7 3
0 2
5 2
6 2
0 3
4 2
4 2
3 2
5 3
6 3
3 0
8 2
9 3
9 3
1 2
1 4
7 2
5 2
5 2
4 0
0 2
...

result:

wrong answer 26th lines differ - expected: '7 2', found: '7 3'
English 繁體中文 简体中文

服务器时间: 2024-12-03 01:32:53 | 开源项目