QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733066#9543. Good PartitionsAlorithmWA 3ms3824kbC++173.6kb2024-11-10 17:01:532024-11-10 17:01:54

Judging History

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

  • [2024-11-10 17:01:54]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3824kb
  • [2024-11-10 17:01:53]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using i64 = long long;

struct SegTree {
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid ((l + r) >> 1)

    int n;
    vector<int> val, g;

    SegTree(int N = 0) : n(N) {
        val.resize(n << 2 | 1);
        g.resize(n << 2 | 1);
    }

    void updata(int p) {
        g[p] = gcd(g[ls], g[rs]);
    }

    void add(int x, int k, int p, int l, int r) {
        if (l == r) {
            val[p] += k;
            if (val[p] > 0)
                g[p] = x;
            else
                g[p] = 0;
            return;
        }

        if (x <= mid)
            add(x, k, ls, l, mid);
        else
            add(x, k, rs, mid + 1, r);
        updata(p);
    }

    int query() {
        return g[1];
    }
};

const int MAXN = 2e5 + 5;
vector<int> fac(MAXN);

void init() {
    for (int i = 1; i <= MAXN; i++)
        for (int j = i; j <= MAXN; j += i)
            fac[j]++;
}

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    using pii = pair<int, int>;
    set<pii> s; // left, right
    int l = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] >= a[i - 1])
            continue;
        s.insert({ l, i - 1 });
        l = i;
    }
    s.insert({ l, n });

    // for (auto [l, r] : s)
    //     cout << l << ' ' << r << endl;

    SegTree tr(n);
    for (auto it = s.begin(); it != s.end(); it++) {
        if (next(it) != s.end()) {
            // cout << it->first << ' ' << it->second << endl;
            int len = it->second - it->first + 1;
            tr.add(len, 1, 1, 1, n);
        }

    }
    cout << fac[tr.query()] << endl;

    auto ist = [&](int l, int r) {
        int len = r - l + 1;
        auto pos = s.insert({ l, r }).first;
        if (next(pos) != s.end())
            tr.add(len, 1, 1, 1, n);
        return pos;
    };

    auto rmv = [&](set<pii>::iterator pos) {
        int l = pos->first;
        int r = pos->second;
        int len = r - l + 1;
        if (next(pos) != s.end())
            tr.add(len, -1, 1, 1, n);
        s.erase(pos);
    };

    while (q--) {
        int p, v;
        cin >> p >> v;
        auto pos = prev(s.lower_bound(make_pair(p + 1, 0)));
        int l = pos->first;
        int r = pos->second;
        int len = r - l + 1;

        rmv(pos);
        if (p < r)
            ist(p + 1, r);
        auto pp = ist(p, p);
        if (l < p)
            ist(l, p - 1);
        a[p] = v;
        // for (auto [l, r] : s)
        //     cout << l << ' ' << r << endl;
        int r1 = p;

        if (p < n && a[p] <= a[p + 1]) {
            auto p2 = next(pp);
            int l2 = p2->first, r2 = p2->second;
            int len2 = r2 - l2 + 1;
            rmv(p2);
            rmv(pp);
            pp = ist(p, r2);
            r1 = r2;
        }

        // cout << endl;
        // for (auto [l, r] : s)
        //     cout << l << ' ' << r << endl;

        if (p > 1 && a[p - 1] <= a[p]) {
            auto p2 = prev(pp);
            int l2 = p2->first, r2 = p2->second;
            int len2 = r2 - l2 + 1;
            rmv(pp);
            rmv(p2);
            pp = ist(l2, r1);
        }

        // for (auto [l, r] : s)
        //     cout << l << ' ' << r << endl;

        cout << fac[tr.query()] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3660kb

input:

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

output:

1
2
3

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3824kb

input:

1
1 1
2000000000
1 1999999999

output:

0
0

result:

wrong answer 1st lines differ - expected: '1', found: '0'