QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#736046#9543. Good Partitionsucup-team1412RE 3ms9540kbC++233.2kb2024-11-11 23:49:452024-11-11 23:49:47

Judging History

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

  • [2024-11-11 23:49:47]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:9540kb
  • [2024-11-11 23:49:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const ll maxn = 1e5 + 10;
const ll inf = 3e9;
vector<ll> loc;
ll aa[maxn];
ll n, q;
ll yinzi[maxn];

ll sum[maxn << 2];
ll add[maxn << 2];

ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}

void push_up(ll rt) {
    sum[rt] = gcd(sum[rt << 1], sum[rt << 1 | 1]);
}

// void push_down(ll rt, ll l, ll r) {
//     if (add[rt]) {
//         add[rt << 1] = gcd(add[rt << 1], add[rt]);
//         add[rt << 1 | 1] = gcd(add[rt << 1 | 1], add[rt]);
//         sum[rt << 1] = gcd(sum[rt << 1], add[rt]);
//         sum[rt << 1 | 1] == gcd(sum[rt << 1 | 1], add[rt]);
//         add[rt] = 0;
//     }
// }

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1

void build(ll l, ll r, ll rt) {
    // add[rt] = 0;
    if (l == r) {
        if (aa[l] > aa[l + 1]) sum[rt] = l;
        else sum[rt] = 0;
        return;
    }
    ll mid = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(ll l, ll r, ll c, ll pos, ll rt) {
    ll mid = (l + r) >> 1;
    if (l == r) {
        sum[rt] = c;
        return;
    }
    if (pos <= mid) update(l, mid, c, pos, rt << 1);
    else update(r, mid + 1, c, pos, rt << 1 | 1);
    push_up(rt);
}

ll query(ll a, ll b, ll l, ll r, ll rt) {
    if (a <= l && b >= r)
        return sum[rt];
    // push_down(rt, l, r);
    ll mid = (l + r) >> 1;
    ll ans = 0;
    if (a <= mid)
        ans = gcd(ans, query(a, b, lson));
    if (b > mid)
        ans = gcd(ans, query(a, b, rson));
    return ans;
}

vector<ll> pri;
bool not_prime[maxn];
ll d[maxn], num[maxn];

void pre(ll n) {
    d[1] = 1;
    for (ll i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            pri.push_back(i);
            d[i] = 2;
            num[i] = 1;
        }
        for (ll pri_j : pri) {
            if (i * pri_j > n) break;
            not_prime[i * pri_j] = true;
            if (i % pri_j == 0) {
                num[i * pri_j] = num[i] + 1;
                d[i * pri_j] = d[i] / num[i * pri_j] * (num[i * pri_j] + 1);
                break;
            }
            num[i * pri_j] = 1;
            d[i * pri_j] = d[i] * 2;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // cout << gcd(6, 9) << ' ' << gcd(3, 18) << ' ' << gcd(1, 189);
    ll t;
    cin >> t;
    pre(maxn);
    while (t--) {
        cin >> n >> q;
        for (ll i = 1; i <= n; i++) {
            cin >> aa[i];
        }
        aa[n + 1] = inf;
        build(1, n, 1);
        ll ans = query(1, n, 1, n, 1);
        if (ans == 0) ans = n;
        else ans = d[ans];
        cout << ans << endl;
        while (q--) {
            ll x, y;
            cin >> x >> y;
            if (y > aa[x + 1])update(1, n, x, x, 1);
            else update(1, n, 0, x, 1);
            if (aa[x - 1] > y)update(1, n, x - 1, x - 1, 1);
            else if (x > 1) update(1, n, 0, x - 1, 1);
            ans = query(1, n, 1, n, 1);
            if (ans == 0) ans = n;
            else ans = d[ans];
            cout << ans << endl;
        }
    }
    return 0;
}

详细

Test #1:

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

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: 0ms
memory: 8220kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: -100
Runtime Error

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: