QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#649932#6836. A Plus B ProblemljljljljTL 290ms112528kbC++207.1kb2024-10-18 11:35:502024-10-18 11:35:50

Judging History

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

  • [2024-10-18 11:35:50]
  • 评测
  • 测评结果：TL
  • 用时：290ms
  • 内存：112528kb
查看
  • [2024-10-18 11:35:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int, int> pii;
struct node
{
    int l, r, sum9, sum0, val, lazy0, lazy9;
};
vector<node> tree(4001000);
string s1, s2, s3;
void puup(int u)
{
    tree[u].sum0 = tree[u << 1].sum0 + tree[u << 1 | 1].sum0;
    tree[u].sum9 = tree[u << 1 | 1].sum9 + tree[u << 1].sum9;
}
void pushdown(int u)
{
    if (tree[u].lazy9)
    {
        tree[u << 1].sum9 = (tree[u << 1].r - tree[u << 1].l + 1);
        tree[u << 1 | 1].sum9 = (tree[u << 1 | 1].r - tree[u << 1 | 1].l + 1);
        tree[u << 1].sum0 = 0;
        tree[u << 1 | 1].sum0 = 0;
        tree[u << 1].val = 9;
        tree[u << 1 | 1].val = 9;
        tree[u].lazy9 = 0;
        tree[u << 1].lazy9 = 1;
        tree[u << 1 | 1].lazy9 = 1;
        tree[u << 1].lazy0 = 0;
        tree[u << 1 | 1].lazy0 = 0;
    }
    if (tree[u].lazy0)
    {
        tree[u << 1].sum0 = (tree[u << 1].r - tree[u << 1].l + 1);
        tree[u << 1 | 1].sum0 = (tree[u << 1 | 1].r - tree[u << 1 | 1].l + 1);
        tree[u << 1].sum9 = 0;
        tree[u << 1 | 1].sum9 = 0;
        tree[u << 1].val = 0;
        tree[u << 1 | 1].val = 0;
        tree[u].lazy0 = 0;
        tree[u << 1].lazy0 = 1;
        tree[u << 1 | 1].lazy0 = 1;
        tree[u << 1].lazy9 = 0;
        tree[u << 1 | 1].lazy9 = 0;
    }
}
void build(int l, int r, int u)
{
    tree[u] = {l, r, 0, 0, s3[l] - '0', 0, 0};
    if (l == r)
    {
        tree[u].sum0 = (s3[l] == '0');
        tree[u].sum9 = (s3[l] == '9');
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, u << 1);
    build(mid + 1, r, u << 1 | 1);
    puup(u);
}
void change1(int l, int r, int u, int val) // 区间修改
{
    int cl = tree[u].l, cr = tree[u].r;
    if (l <= cl && r >= cr)
    {
        if (val == 9)
        {
            tree[u].lazy9 = 1;
            tree[u].lazy0 = 0;
            tree[u].sum9 = cr - cl + 1;
            tree[u].sum0 = 0;
            tree[u].val = 9;
        }
        else if (val == 0)
        {
            tree[u].lazy0 = 1;
            tree[u].lazy9 = 0;
            tree[u].sum0 = cr - cl + 1;
            tree[u].sum9 = 0;
            tree[u].val = 0;
        }
        return;
    }
    pushdown(u);
    int mid = (cl + cr) / 2;
    if (l <= mid)
        change1(l, r, u << 1, val);
    if (r > mid)
        change1(l, r, u << 1 | 1, val);
    puup(u);
}
void change2(int l, int u, int val) // 单点修改
{
    if (l <= 0) // 防止越界
        return;
    int cl = tree[u].l, cr = tree[u].r;
    if (cl == cr && l == cl)
    {
        tree[u].val = val;
        tree[u].sum0 = (val == 0);
        tree[u].sum9 = (val == 9);
        return;
    }
    int mid = (cl + cr) / 2;
    if (l <= mid)
        change2(l, u << 1, val);
    else
        change2(l, u << 1 | 1, val);
    puup(u);
}
pii quary1(int l, int r, int u) // 区间查询
{
    int cl = tree[u].l, cr = tree[u].r;
    if (l <= cl && r >= cr)
    {
        return {tree[u].sum0, tree[u].sum9};
    }
    pushdown(u);
    pii res = {0, 0};
    int mid = (cl + cr) / 2;
    if (l <= mid)
    {
        pii temp = quary1(l, r, u << 1);
        res.first += temp.first;
        res.second += temp.second;
    }
    if (r > mid)
    {
        pii temp = quary1(l, r, u << 1 | 1);
        res.first += temp.first;
        res.second += temp.second;
    }
    return res;
}
int quary2(int l, int u) // 单点查询
{
    if (l <= 0)
        return 0;
    int cl = tree[u].l, cr = tree[u].r;
    if (cl == cr && l == cl)
    {
        return tree[u].val;
    }
    pushdown(u);
    int mid = (cl + cr) / 2;
    if (l <= mid)
        return quary2(l, u << 1);
    else
        return quary2(l, u << 1 | 1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    cin >> s1 >> s2;
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    s3.resize(s1.size());
    int flag = 0;
    for (int i = s1.size() - 1; i >= 1; i--)
    {
        s3[i] = s1[i] - '0' + s2[i] - '0' + flag;
        flag = 0;
        if (s3[i] >= 10)
        {
            s3[i] %= 10;
            flag = 1;
        }
        s3[i] += '0';
    }
    build(1, s1.size() - 1, 1);
    while (q--)
    {
        int x, y;
        char t;
        cin >> x >> y >> t;
        int temp;
        int ans = 0;
        if (x == 1)
        {
            if (t == s1[y])
            {
                int tt = quary2(y, 1);
                cout << tt << ' ' << 0 << '\n';
                continue;
            }
            temp = t - s1[y];
            s1[y] = t;
        }
        if (x == 2)
        {
            if (t == s2[y])
            {
                int tt = quary2(y, 1);
                cout << tt << ' ' << 0 << '\n';
                continue;
            }
            temp = t - s2[y];
            s2[y] = t;
        }
        int val = quary2(y, 1);
        temp += val;
        if (temp < 10 && temp >= 0)
        {
            change2(y, 1, temp);
            int tt = quary2(y, 1);
            cout << tt << ' ' << 2 << '\n';
            continue;
        }
        else if (temp >= 10)
        {
            change2(y, 1, temp % 10);
            int l = 1, r = y - 1;
            int mid = (l + r) / 2;
            while (l <= r)
            {
                pii su = quary1(mid, y - 1, 1);
                if (su.second >= (y - 1 - mid + 1))
                    r = mid - 1;
                else
                    l = mid + 1;
                mid = (l + r) / 2;
            }
            if (l == y)
            {
                int nn = 3;
                if (y == 1)
                    nn--;
                int v = quary2(y - 1, 1) + 1;
                change2(y - 1, 1, v);
                int tt = quary2(y, 1);
                cout << tt << ' ' << nn << '\n';
                continue;
            }
            ans = 2 + y - 1 - l + 1 + 1;
            if (l == 1)
                ans--;
            change1(l, y - 1, 1, 0);
            change2(l - 1, 1, quary2(l - 1, 1) + 1);
        }
        else
        {
            change2(y, 1, temp + 10);
            int l = 1, r = y - 1;
            int mid = (l + r) / 2;
            while (l <= r)
            {
                pii su = quary1(mid, y - 1, 1);
                if (su.first >= (y - 1 - mid + 1))
                    r = mid - 1;
                else
                    l = mid + 1;
                mid = (l + r) / 2;
            }
            if (l == y)
            {
                int nn = 3;
                if (y == 1)
                    nn--;
                int v = quary2(y - 1, 1) - 1;
                change2(y - 1, 1, v);
                int tt = quary2(y, 1);
                cout << tt << ' ' << nn << '\n';
                continue;
            }
            ans = 2 + y - 1 - l + 1 + 1;
            if (l == 1)
                ans--;
            change1(l, y - 1, 1, 9);
            change2(l - 1, 1, quary2(l - 1, 1) - 1);
        }
        int kk = quary2(y, 1);
        cout << kk << ' ' << ans << '\n';
    }
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 21ms
memory: 112432kb

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: 4ms
memory: 112344kb

input:

1 1
1
1
1 1 9

output:

0 2

result:

ok single line: '0 2'

Test #3:

score: 0
Accepted
time: 222ms
memory: 112424kb

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

ok 1000000 lines

Test #4:

score: 0
Accepted
time: 285ms
memory: 112528kb

input:

10 1000000
8702774998
9088637390
1 3 3
2 4 7
1 4 0
1 6 7
1 1 1
1 4 0
2 3 8
1 7 7
2 4 5
2 4 2
1 8 2
2 6 7
1 1 2
1 1 4
1 10 3
1 2 3
1 2 5
1 4 8
1 6 5
1 9 8
1 1 9
1 2 1
1 8 5
1 8 3
1 7 1
1 9 7
1 10 7
1 8 5
1 5 1
2 6 4
1 6 1
2 10 2
1 10 5
2 10 1
1 9 3
2 2 0
1 1 0
1 6 6
2 2 5
2 4 4
2 5 6
2 7 4
1 2 5
2 4 ...

output:

2 3
0 2
8 3
1 0
0 2
8 0
1 0
5 2
6 2
3 2
6 3
5 2
1 2
3 2
3 2
4 2
6 2
1 3
3 2
7 2
8 2
2 2
9 2
7 2
8 3
6 2
7 2
9 2
8 3
9 3
5 2
9 2
7 2
6 2
2 2
2 0
9 2
0 3
7 2
2 2
8 0
5 2
1 3
0 2
2 3
3 2
0 2
3 3
2 2
0 2
2 0
5 2
1 2
3 2
4 3
6 0
6 2
2 2
1 2
6 3
0 2
7 2
7 3
4 0
3 2
8 2
3 2
4 0
8 3
8 2
4 2
5 2
5 2
5 2
7 2
...

result:

ok 1000000 lines

Test #5:

score: 0
Accepted
time: 220ms
memory: 112232kb

input:

10 1000000
6869373857
3130626142
1 3 2
1 8 6
1 8 8
1 3 6
1 1 6
1 1 6
2 5 3
2 5 6
2 4 2
2 5 7
2 5 6
2 4 0
2 5 0
2 5 6
1 3 7
1 3 6
2 7 0
2 1 6
2 1 3
2 7 6
2 5 8
2 6 6
2 5 2
2 5 8
2 3 3
2 2 1
2 2 1
2 3 3
2 4 0
2 5 4
2 5 8
2 4 0
2 6 2
2 1 2
2 1 3
1 1 8
2 3 9
2 3 3
1 1 6
2 5 6
2 7 7
1 4 6
1 1 2
1 1 6
1 4...

output:

5 2
7 2
9 2
9 2
9 0
9 0
6 2
9 2
1 5
0 3
9 3
9 5
3 2
9 2
0 4
9 4
3 2
2 2
9 2
9 2
1 6
3 3
6 6
2 6
0 0
0 0
0 0
0 0
0 0
8 6
2 6
0 0
9 3
9 2
0 2
2 2
6 2
0 2
0 2
9 6
0 8
7 5
5 2
9 2
0 5
9 8
5 2
3 5
5 2
9 2
9 5
9 2
8 2
9 2
7 2
9 2
3 10
8 3
0 3
9 10
8 2
5 2
2 4
6 2
4 4
6 3
3 3
9 3
3 2
5 4
7 2
6 2
8 2
1 3
9 ...

result:

ok 1000000 lines

Test #6:

score: 0
Accepted
time: 290ms
memory: 112528kb

input:

10 1000000
6869373857
3130626142
1 9 6
1 9 5
1 10 8
1 10 7
2 7 8
2 7 6
1 6 8
1 6 7
1 7 8
1 7 3
2 10 4
2 10 2
2 8 3
2 8 1
2 9 7
2 9 4
2 9 9
2 9 4
2 7 7
2 7 6
1 7 4
1 7 3
1 9 6
1 9 5
1 8 9
1 8 8
1 7 5
1 7 3
1 6 9
1 6 7
2 6 8
2 6 2
1 8 9
1 8 8
2 10 6
2 10 2
2 6 9
2 6 2
1 6 9
1 6 7
1 8 9
1 8 8
2 9 7
2 9...

output:

0 10
9 10
0 11
9 11
1 8
9 8
0 7
9 7
4 8
9 8
1 11
9 11
1 9
9 9
2 10
9 10
4 10
9 10
0 8
9 8
0 8
9 8
0 10
9 10
0 9
9 9
1 8
9 8
1 7
9 7
5 7
9 7
0 9
9 9
3 11
9 11
6 7
9 7
1 7
9 7
0 9
9 9
2 10
9 10
2 7
9 7
1 8
9 8
1 11
9 11
4 7
9 7
5 11
9 11
0 7
9 7
0 10
9 10
1 10
9 10
0 7
9 7
2 10
9 10
2 10
9 10
1 11
9 1...

result:

ok 1000000 lines

Test #7:

score: -100
Time Limit Exceeded

input:

1000000 1000000
68693738574822907668000669943297325347608140886272616051068251483556534289323531160993017440087302814083329820936792365202060610991343493080865626095241885616863256382251749215319751373247876361270911203617554820406029584474249635378527788208607403822974202545637490373196507887743784...

output:

4 2
6 2
4 2
5 2
7 97772
8 2
0 140233
6 2
5 2
1 2
1 70008
8 2
1 987
0 138405
5 2
6 138113
1 121002
2 35285
4 2
0 2
3 25467
5 2
8 2
4 5543
6 2
1 3862
8 2
3 107304
6 81700
0 0
2 2
0 0
0 15551
5 14120
3 4872
7 2
0 0
6 58933
6 2
9 7954
4 2
4 2
3 63166
0 0
8 38562
1 349
6 10624
3 2
3 2
4 2
8 65159
4 21435...

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 23:45:13 | OpenSource Project