QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736398 | #9543. Good Partitions | dddfff | WA | 144ms | 15988kb | C++23 | 5.5kb | 2024-11-12 10:46:01 | 2024-11-12 10:46:01 |
Judging History
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'