QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#736538#9543. Good PartitionsdddfffWA 206ms22796kbC++235.0kb2024-11-12 11:41:422024-11-12 11:41:43

Judging History

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

  • [2024-11-12 11:41:43]
  • 评测
  • 测评结果:WA
  • 用时:206ms
  • 内存:22796kb
  • [2024-11-12 11:41:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int T;
#define ls n << 1
#define rs n << 1 | 1

int n, m, a[N], len[N];
#define ls (n << 1)
#define rs (n << 1 | 1)

int t[N << 2], lazy[N << 2];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

void pushup(int n)
{
    t[n] = gcd(t[ls], t[rs]);
}

void pushdown(int n)
{
    if (lazy[n])
    {
        lazy[ls] = lazy[rs] = lazy[n];
        t[ls] = t[rs] = lazy[n];
        lazy[n] = 0;
    }
}

void create(int n, int l, int r)
{
    t[n] = 0;
    lazy[n] = 0;
    if (l == r)
    {
        t[n] = len[l];
        return;
    }
    int mi = l + r >> 1;
    create(ls, l, mi);
    create(rs, mi + 1, r);
    pushup(n);
}

void update(int n, int l, int r, int sl, int sr, int w)
{
    if (l > sr || r < sl)
    {
        return;
    }
    if (l >= sl && r <= sr)
    {
        t[n] = w;
        lazy[n] = w;
        return;
    }
    int mi = l + r >> 1;
    pushdown(n);
    update(ls, l, mi, sl, sr, w);
    update(rs, mi + 1, r, sl, sr, w);
    pushup(n);
}

int answer(int n, int l, int r, int sl, int sr)
{
    if (l > sr || r < sl)
    {
        return 0;
    }
    if (l >= sl && r <= sr)
    {
        return t[n];
    }
    int mi = l + r >> 1;
    pushdown(n);
    int g = 0;
    g = gcd(g, answer(ls, l, mi, sl, sr));
    g = gcd(g, answer(rs, mi + 1, r, sl, sr));
    return g;
}
long long cnt[N];
void init()
{
    for (int i = 1; i <= 200001; i++)
        for (int j = 1; j * i <= 200001; j++)
            cnt[i * j]++;
}
set<int> st;
int rpos[N];
void solve()
{
    // code
    st.clear();
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        rpos[i] = 0;
        len[i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        int j = i;
        while (j + 1 <= n && a[j] <= a[j + 1])
        {
            j++;
        }
        for (int k = i; k <= j; k++)
        {
            len[k] = (j - i + 1);
        }
        st.insert(i);
        rpos[i] = j;
        i = j;
    }
    create(1, 1, n);
    int l = *st.rbegin();
    int g = answer(1, 1, n, 1, l - 1);
    if (g == 0 || l == 1)
    {
        cout << n << '\n';
    }
    else
    {
        cout << cnt[g] << '\n';
    }
    while (m--)
    {
        int pos, v;
        cin >> pos >> v;
        a[pos] = v;
        auto nl = st.lower_bound(pos);
        int l = *nl, r = rpos[l];
        if (l <= pos - 1)
        {
            rpos[l] = pos - 1;
            update(1, 1, n, l, pos - 1, pos - l);
        }
        st.insert(pos);
        rpos[pos] = pos;
        update(1, 1, n, pos, pos, 1);
        if (pos + 1 <= r)
        {
            st.insert(pos + 1);
            rpos[pos + 1] = r;
            update(1, 1, n, pos + 1, r, r - pos);
        }
        nl = st.find(pos);
        if (*nl == *st.begin() && *nl == *st.rbegin())
        {
            cout << 1 << '\n';
            continue;
        }
        if (*nl == *st.begin())
        {
            auto rq = nl;
            rq++;
            int rl = *rq, rr = rpos[rl];
            if (a[pos] <= a[rl])
            {
                st.erase(rl);
                rpos[pos] = rr;
                update(1, 1, n, pos, rr, rr - pos + 1);
            }
        }
        else if (*nl == *st.rbegin())
        {
            auto lq = nl;
            lq--;
            int ll = *lq, lr = rpos[ll];
            if (a[pos] >= a[lr])
            {
                st.erase(pos);
                rpos[ll] = pos;
                update(1, 1, n, ll, pos, pos - ll + 1);
            }
        }
        else
        {
            auto lq = nl;
            lq--;
            auto rq = nl;
            rq++;
            int l1 = *lq, l2 = rpos[l1];
            int r1 = *rq, r2 = rpos[r1];
            if (a[pos] >= a[l2] && a[pos] <= a[r1])
            {
                st.erase(pos);
                st.erase(r1);
                rpos[l1] = r2;
                update(1, 1, n, l1, r2, r2 - l1 + 1);
            }
            else if (a[pos] >= a[l2])
            {
                st.erase(pos);
                rpos[l1] = pos;
                update(1, 1, n, l1, pos, pos - l1 + 1);
            }
            else if (a[pos] <= a[r1])
            {
                st.erase(r1);
                rpos[pos] = r2;
                update(1, 1, n, pos, r2, r2 - pos + 1);
            }
        }
        int x = *st.rbegin();
        int g = answer(1, 1, n, 1, x - 1);
        if (g == 0 || x == 1)
        {
            cout << n << '\n';
        }
        else
        {
            cout << cnt[g] << '\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 9868kb

input:

1
5 2
4 3 2 6 1
2 5
3 5

output:

1
2
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 10640kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 155ms
memory: 13868kb

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:

160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160
200000
160...

result:

ok 200001 lines

Test #4:

score: 0
Accepted
time: 206ms
memory: 22796kb

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:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 200001 lines

Test #5:

score: 0
Accepted
time: 159ms
memory: 13708kb

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:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 200001 lines

Test #6:

score: 0
Accepted
time: 4ms
memory: 10024kb

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:

2
2
1
1
1
1
1
1
1
1
1
1

result:

ok 12 lines

Test #7:

score: 0
Accepted
time: 4ms
memory: 10056kb

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:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
1
2
1
2
2
2
2
2
2
1
1
1
1
2
1
2
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 110 lines

Test #8:

score: -100
Wrong Answer
time: 5ms
memory: 10328kb

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:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

wrong answer 699th lines differ - expected: '1', found: '3'