QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#738367	#9543. Good Partitions	absabs	WA	360ms	38060kb	C++23	14.9kb	2024-11-12 18:52:05	2024-11-12 18:52:07

Judging History

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

[2024-11-12 18:52:07]
评测

测评结果：WA
用时：360ms
内存：38060kb

查看

[2024-11-12 18:52:05]
提交

answer

// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "D:/OneDrive/study/cpp/.vscode/debug.h"
#else
#define debug(...) 42;
#endif
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ll __int128_t
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e6 + 10;
const double eps = 1e-6;
int arr[MAXN], w[MAXN];
int n, q;
struct Node
{
    int l, r;
    int sum, d;
} tr[MAXN * 4];
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r) // 算左右两边的信息
{                                      // 节点和两个儿子
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
    return;
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
    return ;
}
void build(int u, int l, int r)
{
    if (l == r)
    {
        int b = w[r] - w[r - 1]; // 存进去的是差分数组,由辗转除法可知,两数的最大公约数和一个数与两数差的最大公约数一致
        tr[u] = {l, r, b, b};
        return;
    }
    else
    {
        // tr[u].l = l, tr[u].r = r;
        tr[u] = {l,r,0,0};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        int b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
        return ;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)
            modify(u << 1, x, v);
        else
            modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
Node query(int u, int l, int r)
{
    if (l > r)
        return Node{0, 0, 0, 0};
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u]; // 在区间内部
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid)
            return query(u << 1, l, r); // 都在左半边
        else if (l > mid)
            return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res = {0, 0, 0, 0};
            pushup(res, left, right);
            return res;
        }
    }
}
void fun()
{
    if (n == 1)
    {
        cout << n << endl;
        return;
    }
    if (n == 2)
    {
        if (w[2] == 2)
            cout << 2 << endl;
        else
            cout << 1 << endl;
        return;
    }
    auto left = query(1, 1, 1);          /// 求1到l的前缀和
    auto right = query(1, 1 + 1, n - 1); // 最大公约数
    int d = abs(gcd(left.sum, right.d)), now = w[n], cnt = 0;
    // cout << d << " eeeee " << now << " " << cnt << endl;
    for (int i = 1; i <= sqrt(d); i++)
    {
        // if (i > now)
        //     break;
        if (d % i == 0)
        {
            cnt++;
            int tp = d / i;
            if (tp != i)
                cnt++;
        }
    }
    if (d == 0)
        cout << n << endl;
    else
        cout << cnt << endl;
    return ;
}
void solve()
{
    cin >> n >> q;
    int cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++)
        w[i] = 0;
    set<int> st;
    for (int i = 2; i <= n; i++)
    {
        if (arr[i] < arr[i - 1])
        {
            w[i - 1] = cnt;
            cnt = 1;
            st.insert(i - 1);
        }
        else
            cnt++;
    }
    w[n] = cnt;
    st.insert(n);
    arr[0] = w[0] = 0;
    int indx, x;
    build(1, 1, n);
    fun();
    while (q--)
    {
        cin >> indx >> x;
        arr[indx] = x;
        if (w[indx])
        {
            if (w[indx] == 1)
            {
                if (indx == 1)
                {
                    if (arr[1] <= arr[2])
                    {
                        int d = -w[1];
                        w[1] = 0;
                        modify(1, 1, d);
                        if (1 + 1 <= n)
                            modify(1, 2, -d);
                        auto tp = st.upper_bound(indx);
                        int t = *tp;
                        // int t = upper_bound(w + 1, w + 1 + n, 0) - w;
                        w[t] += 1;
                        d = 1;
                        modify(1, t, d);
                        if (t + 1 <= n)
                            modify(1, t + 1, -d);
                        if(st.count(1)) st.erase(1);
                    }
                    fun();
                    continue;
                }
                else if (indx == n)
                {
                    if (n - 1 >= 1 && arr[n] >= arr[n - 1])
                    {
                        int d = w[n - 1];
                        w[n] += d;
                        modify(1, n, d);
                        w[n - 1] = 0;
                        d = -d;
                        if(n - 1 >= 1)
                            modify(1, n - 1, d);
                        modify(1, n, -d);
                        // if(!st.count(n)) st.insert(n);
                        if(w[n - 1] == 0) st.erase(n - 1);
                    }
                    else if(n - 1 >= 1 && arr[n - 1] > arr[n])
                    {
                        int d = w[n] - 1;
                        w[n - 1] += d;
                        modify(1,n - 1,d);
                        modify(1,n,-d);
                        w[n] = 1;
                        d = -d;
                        modify(1,n,d);
                        if(!st.count(n - 1)) st.insert(n - 1);
                    }
                    fun();
                    continue;
                }
                if (indx - 1 >= 1 && indx + 1 <= n && arr[indx - 1] <= arr[indx] && arr[indx] <= arr[indx + 1])
                {
                    int sum = w[indx - 1];
                    int d = -w[indx - 1];
                    w[indx - 1] = 0;
                    if(indx > 1)
                        modify(1, indx - 1, d);
                    if (indx <= n)
                        modify(1, indx, -d);
                    st.erase(indx - 1);
                    d = -w[indx];
                    sum += w[indx];
                    w[indx] = 0;
                    modify(1, indx, d);
                    if (indx + 1 <= n)
                        modify(1, indx + 1, -d);
                    st.erase(indx);
                    // int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
                    auto tp = st.upper_bound(indx);
                    int t = *tp;
                    w[t] += sum;
                    d = sum;
                    // if(!st.count(t)) st.insert(t);
                    modify(1, t, d);
                    if (t + 1 <= n)
                        modify(1, t + 1, -d);
                }
                else if (indx - 1 >= 1 && arr[indx - 1] <= arr[indx])
                {
                    int d = -w[indx - 1];
                    w[indx - 1] = 0;
                    if(indx > 1)
                        modify(1, indx - 1, d);
                    if (indx <= n)
                        modify(1, indx, -d);
                    if(st.count(indx - 1)) st.erase(indx - 1);
                    auto tp = st.lower_bound(indx);
                    int t = *tp;
                    d = -d;
                    w[t] += d;
                    modify(1, t, d);
                    if (t + 1 <= n) 
                        modify(1, t + 1, -d);
                    // if(!st.count(indx)) st.insert(indx);
                }
                else if (indx + 1 <= n && arr[indx] <= arr[indx + 1])
                {
                    int d = -w[indx];
                    w[indx] = 0;
                    modify(1, indx, d);
                    if (indx + 1 <= n)
                        modify(1, indx + 1, -d);
                    st.erase(indx);
                    auto tp = st.upper_bound(indx); 
                    // int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
                    int t = *tp;
                    d = -d;
                    w[t] += d;
                    modify(1, t, d);
                    if (t + 1 <= n)
                        modify(1, t + 1, -d);
                    // if(!st.count(t)) st.insert(indx);
                }
            }
            else
            {
                if (indx == n)
                {
                    if (indx == 1)
                    {
                        continue;
                    }
                    if (arr[n - 1] > arr[n])
                    {
                        int d = w[n] - 1;
                        w[n - 1] += d;
                        modify(1, n - 1, d);
                        // if(n <= n)
                        modify(1, n, -d);
                        d = -d;
                        w[n] = 1;
                        modify(1, n, d);
                        if(!st.count(n - 1)) st.insert(n - 1);
                    }
                }
                else
                {
                    if (indx > 1 && arr[indx] < arr[indx - 1]) // 断开
                    {
                        int d = w[indx] - 1;
                        w[indx - 1] += d;
                        modify(1, indx - 1, d);
                        if (indx <= n)
                            modify(1, indx, -d);
                        d = -d;
                        w[indx] = 1;
                        modify(1, indx, d);
                        if (indx + 1 <= n)
                            modify(1, indx + 1, -d);
                        if(!st.count(indx - 1)) st.insert(indx - 1);
                        // if(!st.count(indx)) st.insert(indx);
                    }
                    if (indx < n && arr[indx] <= arr[indx + 1])
                    {
                        int sum = w[indx]; 
                        int d = -w[indx]; 
                        w[indx] = 0;  
                        modify(1, indx, d);
                        if (indx + 1 <= n)
                            modify(1, indx + 1, -d);
                        st.erase(indx);
                        auto tp = st.upper_bound(indx);
                        int t = *tp;
                        // int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
                        w[t] += sum;
                        d = -d;
                        modify(1, t, d);
                        if (t + 1 <= n)
                            modify(1, t + 1, -d);
                    }
                }
            }
        }
        else
        {
            if (indx == 1 && arr[1] > arr[2])
            {
                // int t = upper_bound(w + 1, w + 1 + n, 0) - w;
                auto tp = st.upper_bound(indx);
                int t = *tp;
                w[t]--;
                int d = -1;
                modify(1, t, d);
                if (t + 1 <= n)
                    modify(1, t + 1, -d);
                d = 1;
                w[1] = 1;
                modify(1, 1, d);
                if (2 <= n)
                    modify(1, 2, -d);
                if(!st.count(1)) st.insert(1);
            }
            else
            {
                if (indx < n && arr[indx] > arr[indx + 1])//断开
                {
                    // int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
                    auto tp = st.upper_bound(indx);
                    int t = *tp;
                    int sum = w[t];
                    int R = t - indx;
                    int L = w[t] - R;
                    int d = L;
                    // int d = w[t] - (t - indx) - w[indx];
                    w[indx] += L;
                    modify(1, indx, d);
                    if (indx + 1 <= n)
                        modify(1, indx + 1, -d);
                    d = R - w[t];
                    w[t] += d;
                    modify(1, t, d);
                    if (t + 1 <= n)
                        modify(1, t + 1, -d);
                    st.insert(indx);
                    if(w[t] == 0) st.erase(t);
                }
                if (indx > 1 && arr[indx - 1] > arr[indx] && !w[indx - 1]) // 断开
                {
                    auto tp = st.lower_bound(indx);
                    int t = *tp;
                    int R = t - indx + 1,L = w[t] - R;
                    int d = L;
                    w[indx - 1] += L;
                    modify(1, indx - 1, d);
                    if (indx <= n)
                        modify(1, indx, -d);
                    if(w[indx - 1]) st.insert(indx - 1);
                    d = R - w[t];;
                    w[t] += d;
                    modify(1, t, d);
                    if (t + 1 <= n)
                        modify(1, t + 1, -d);
                    else st.erase(indx - 1);
                    if(w[t] == 0) st.erase(t);
                }
                if (indx > 1 && arr[indx - 1] <= arr[indx])
                {
                    auto tp = st.lower_bound(indx);
                    int t = *tp;
                    int d = -w[indx - 1];
                    w[indx - 1] = 0;
                    modify(1, indx - 1, d);
                    if (indx <= n)
                        modify(1, indx, -d);
                    if(st.count(indx - 1)) st.erase(indx - 1);
                    d = -d;
                    w[t] += d;
                    modify(1, t, d);
                    if (t + 1 <= n)
                        modify(1, t + 1, -d);
                    // if(w[t]) st.insert(t);
                }
                if (indx < n && arr[indx] <= arr[indx + 1])
                {
                    auto tp = st.upper_bound(indx);
                    int t = *tp;
                    int sum = w[indx];
                    int d = -w[indx];
                    w[indx] = 0;
                    modify(1, indx, d);
                    if (indx + 1 <= n)
                        modify(1, indx + 1, -d);
                    // int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
                    // auto tp = st.upper_bound(indx);
                    // int t = *tp;
                    if(st.count(indx)) st.erase(indx);
                    w[t] += sum;
                    d = sum;
                    modify(1, t, d);
                    if (t + 1 <= n)
                        modify(1, t + 1, -d);
                }
            }
        }
        // cout << "\narr :\n";
        // for(int i=1;i<=n;i++)  cout << arr[i] << " ";
        // cout << endl;
        // cout << "\nw :\n";
        // for(int i=1;i<=n;i++) cout << w[i] << " ";
        // cout << endl;
        fun();
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 7640kb

input:

output:

1
2
3

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 1ms

memory: 7892kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 299ms

memory: 25932kb

input:

1
200000 200000
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

result:

ok 200001 lines

Test #4:

score: 0

Accepted

time: 216ms

memory: 38060kb

input:

1
200000 200000
200001 200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 1999...

output:

result:

ok 200001 lines

Test #5:

score: 0

Accepted

time: 360ms

memory: 29152kb

input:

1
200000 200000
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

result:

ok 200001 lines

Test #6:

score: 0

Accepted

time: 0ms

memory: 7632kb

input:

2
2 2
17017 63462
2 94054
2 13504
8 8
14380 5840 34752 73602 60279 26105 44308 78318
7 8597
2 70671
6 56663
5 90093
5 96853
3 10700
1 76875
6 27325

output:

result:

ok 12 lines

Test #7:

score: 0

Accepted

time: 1ms

memory: 7612kb

input:

10
9 15
850456 510799 912572 938543 215712 758501 850577 149454 330027
7 740992
7 73826
1 993823
7 143019
8 152824
2 109975
5 151989
7 851016
3 157534
8 491512
6 987473
7 272348
3 842756
4 278214
5 707564
10 17
494099 922564 124251 422938 100551 915266 18436 74858 885629 897256
8 798574
7 49544
7 83...

output:

result:

ok 110 lines

Test #8:

score: 0

Accepted

time: 2ms

memory: 7752kb

input:

10
133 246
140510 608816 589575 476955 565233 554161 572604 339315 619706 665193 478181 434356 152086 642681 20634 515330 792629 985669 964199 254936 124166 33376 866759 559350 243009 210630 84226 54133 562576 188482 341088 287802 931163 132016 885704 128841 718254 917725 716410 175025 922633 18826 ...

output:

result:

ok 1010 lines

Test #9:

score: 0

Accepted

time: 6ms

memory: 7964kb

input:

10
3872 687
44064166 27154700 47734073 23232952 85900163 60570475 79562375 95316865 5283870 83145253 18727311 84521331 87003172 67383345 87258243 56070949 93690923 24354578 82428308 54239011 31728698 60725336 28686234 19515381 86019850 20774145 91634419 99792041 34779827 43899611 5776212 38860142 22...

output:

result:

ok 10010 lines

Test #10:

score: 0

Accepted

time: 255ms

memory: 15264kb

input:

10
16568 3726
108245963 1072826507 922424573 1724795997 821224456 920893777 1197351187 1750418758 475004108 473502990 1018456990 1361563534 750892494 1656602758 1227777726 25842374 1616734168 755178190 1192059348 549671897 71441917 604937525 380135847 1750880898 478060006 1256638169 469752575 429941...

output:

result:

ok 200010 lines

Test #11:

score: 0

Accepted

time: 258ms

memory: 13284kb

input:

10
49420 24551
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

result:

ok 200010 lines

Test #12:

score: 0

Accepted

time: 272ms

memory: 16156kb

input:

10
10300 2652
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

result:

ok 200010 lines

Test #13:

score: 0

Accepted

time: 249ms

memory: 17840kb

input:

10
28101 16542
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

result:

ok 200010 lines

Test #14:

score: 0

Accepted

time: 339ms

memory: 28708kb

input:

1
200000 200000
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

result:

ok 200001 lines

Test #15:

score: -100

Wrong Answer

time: 314ms

memory: 27668kb

input:

1
200000 200000
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

result:

wrong answer 1712th lines differ - expected: '4', found: '8'