QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#736398#9543. Good PartitionsdddfffWA 144ms15988kbC++235.5kb2024-11-12 10:46:012024-11-12 10:46:01

Judging History

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

  • [2024-11-12 10:46:01]
  • 评测
  • 测评结果:WA
  • 用时:144ms
  • 内存:15988kb
  • [2024-11-12 10:46:01]
  • 提交

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 u << 1
#define rs u << 1 | 1
struct tree
{
    int l, r, w, lazy;
} tr[N * 4];
int n, m, a[N], len[N];
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
void pushup(int u)
{
    tr[u].w = gcd(tr[ls].w, tr[rs].w);
}
void pushdown(int u)
{
    if (tr[u].lazy)
    {
        tr[ls].w = tr[rs].w = tr[u].lazy;
        tr[ls].lazy = tr[rs].lazy = tr[u].lazy;
        tr[u].lazy = 0;
    }
}
void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, l, len[l], 0};
        return;
    }
    tr[u] = {l, r, 0, 0};
    long long mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}
void update(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].w = v;
        tr[u].lazy = v;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid)
            update(ls, l, r, v);
        if (r > mid)
            update(rs, l, r, v);
        pushup(u);
    }
}
int ask(int u, int l, int r)
{
    if (l > r)
    {
        return 0;
    }
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].w;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        int ans = 0;
        if (l <= mid)
            ans = gcd(ans, ask(ls, l, r));
        if (r > mid)
            ans = gcd(ans, ask(rs, l, r));
        return ans;
    }
}
vector<int> p;
bool np[N];
void init()
{
    for (int i = 2; i < N; i++)
    {
        if (!np[i])
        {
            p.push_back(i);
        }
        for (auto j : p)
        {
            if (i * j >= N)
            {
                break;
            }
            np[i * j] = true;
            if (i % j == 0)
            {
                break;
            }
        }
    }
}
int getans(int x)
{
    int ans = 1;
    for (auto i : p)
    {
        int num = 0;
        while (x != 1 && x % i == 0)
        {
            num++;
            x /= i;
        }
        ans *= num + 1;
        if (x == 1)
        {
            break;
        }
    }
    return ans;
}
set<int> st;
int rpos[N];
void solve()
{
    // code
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    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;
    }
    build(1, 1, n);
    int l = *st.rbegin();
    int g = ask(1, 1, l - 1);
    if (g == 0)
    {
        cout << n << '\n';
    }
    else
    {
        cout << getans(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, l, pos - 1, pos - l);
        }
        rpos[pos] = pos;
        update(1, pos, pos, 1);
        if (pos + 1 <= r)
        {
            st.insert(pos + 1);
            rpos[pos + 1] = r;
            update(1, pos + 1, r, r - pos);
        }
        nl = st.lower_bound(pos);
        auto en = st.end();
        en--;
        if (nl == st.begin() && nl == en)
        {
            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, pos, rr, rr - pos + 1);
            }
        }
        else if (nl == en)
        {
            auto lq = nl;
            lq--;
            int ll = *lq, lr = rpos[ll];
            if (a[pos] >= a[lr])
            {
                st.erase(pos);
                rpos[ll] = pos;
                update(1, 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, l1, r2, r2 - l1 + 1);
            }
            else if (a[pos] >= a[l2])
            {
                st.erase(pos);
                rpos[l1] = pos;
                update(1, l1, pos, pos - l1 + 1);
            }
            else if (a[pos] <= a[r1])
            {
                st.erase(r1);
                rpos[pos] = r2;
                update(1, pos, r2, r2 - pos + 1);
            }
        }
        int x = *st.rbegin();
        int g = ask(1, 1, x - 1);
        if (g == 0)
        {
            cout << n << '\n';
        }
        else
        {
            cout << getans(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: 1ms
memory: 5768kb

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: 1ms
memory: 6036kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: -100
Wrong Answer
time: 144ms
memory: 15988kb

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
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
160
...

result:

wrong answer 2nd lines differ - expected: '200000', found: '160'