QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #736865 | #9543. Good Partitions | absabs | WA | 362ms | 37584kb | C++23 | 14.2kb | 2024-11-12 13:44:49 | 2024-11-12 13:44:50 |
Judging History
answer
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "D:/OneDrive/study/cpp/.vscode/debug.h"
#else
#define debug(...) 42;
#endif
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ll __int128_t
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e6 + 10;
const double eps = 1e-6;
int arr[MAXN], w[MAXN];
int n, q;
struct Node
{
int l, r;
int sum, d;
} tr[MAXN * 4];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r) // 算左右两边的信息
{ // 节点和两个儿子
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
return;
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
return ;
}
void build(int u, int l, int r)
{
if (l == r)
{
int b = w[r] - w[r - 1]; // 存进去的是差分数组,由辗转除法可知,两数的最大公约数和一个数与两数差的最大公约数一致
tr[u] = {l, r, b, b};
return;
}
else
{
// tr[u].l = l, tr[u].r = r;
tr[u] = {l,r,0,0};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x)
{
int b = tr[u].sum + v;
tr[u] = {x, x, b, b};
return ;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid)
modify(u << 1, x, v);
else
modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (l > r)
return Node{0, 0, 0, 0};
if (tr[u].l >= l && tr[u].r <= r)
return tr[u]; // 在区间内部
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
return query(u << 1, l, r); // 都在左半边
else if (l > mid)
return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res = {0, 0, 0, 0};
pushup(res, left, right);
return res;
}
}
}
void fun()
{
if (n == 1)
{
cout << n << endl;
return;
}
if (n == 2)
{
if (w[2] == 2)
cout << 2 << endl;
else
cout << 1 << endl;
return;
}
auto left = query(1, 1, 1); /// 求1到l的前缀和
auto right = query(1, 1 + 1, n - 1); // 最大公约数
int d = abs(gcd(left.sum, right.d)), now = w[n], cnt = 0;
// cout << d << " eeeee " << now << " " << cnt << endl;
for (int i = 1; i <= sqrt(d); i++)
{
// if (i > now)
// break;
if (d % i == 0)
{
cnt++;
int tp = d / i;
if (tp != i)
cnt++;
}
}
if (d == 0)
cout << n << endl;
else
cout << cnt << endl;
return ;
}
void solve()
{
cin >> n >> q;
int cnt = 1;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
for (int i = 1; i <= n; i++)
w[i] = 0;
set<int> st;
for (int i = 2; i <= n; i++)
{
if (arr[i] < arr[i - 1])
{
w[i - 1] = cnt;
cnt = 1;
st.insert(i - 1);
}
else
cnt++;
}
w[n] = cnt;
st.insert(n);
arr[0] = w[0] = 0;
int indx, x;
build(1, 1, n);
fun();
while (q--)
{
cin >> indx >> x;
arr[indx] = x;
// cout << "begin\n";
// for(auto L : st)
// cout << L << " ";
// cout << "\nend\n";
if (w[indx])
{
if (w[indx] == 1)
{
if (indx == 1)
{
if (arr[1] <= arr[2])
{
int d = -w[1];
w[1] = 0;
if(st.count(1)) st.erase(1);
modify(1, 1, d);
if (1 + 1 <= n)
modify(1, 2, -d);
auto tp = st.upper_bound(indx);
int t = *tp;
// int t = upper_bound(w + 1, w + 1 + n, 0) - w;
w[t] += 1;
d = 1;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
fun();
continue;
}
else if (indx == n)
{
if (n - 1 >= 1 && arr[n] >= arr[n - 1])
{
w[n] += 1;
modify(1, n, 1);
if(!st.count(n)) st.insert(n);
w[n - 1]--;
if(w[n - 1] == 0) st.erase(n - 1);
if(n - 1 >= 1)
modify(1, n - 1, -1);
modify(1, n, 1);
}
fun();
continue;
}
if (indx - 1 >= 1 && indx + 1 <= n && arr[indx - 1] <= arr[indx] && arr[indx] <= arr[indx + 1])
{
int sum = w[indx - 1] + 1;
int d = -w[indx - 1];
w[indx - 1] = 0;
st.erase(indx - 1);
if(indx > 1)
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = -w[indx];
w[indx] = 0;
st.erase(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
w[t] += sum;
d = sum;
// if(!st.count(t)) st.insert(t);
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
else if (indx - 1 >= 1 && arr[indx - 1] <= arr[indx])
{
w[indx] += w[indx - 1];
int d = w[indx - 1];
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = -w[indx - 1];
w[indx - 1] = 0;
if(st.count(indx - 1)) st.erase(indx - 1);
if(!st.count(indx)) st.insert(indx);
if(indx > 1)
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
}
else if (indx + 1 <= n && arr[indx] <= arr[indx + 1])
{
int d = -w[indx];
w[indx] = 0;
if(st.count(indx)) st.insert(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
auto tp = st.upper_bound(indx);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
int t = *tp;
w[t]++;
modify(1, t, 1);
if (t + 1 <= n)
modify(1, t + 1, -1);
}
}
else
{
if (indx == n)
{
if (indx == 1)
{
continue;
}
if (arr[n - 1] > arr[n])
{
int d = w[n] - 1 - w[n - 1];
w[n - 1] = w[n] - 1;
if(!st.count(n - 1)) st.insert(n - 1);
modify(1, n - 1, d);
// if(n <= n)
modify(1, n, -d);
d = 1 - w[n];
w[n] = 1;
modify(1, n, d);
}
}
else
{
if (indx > 1 && arr[indx] < arr[indx - 1])
{
int d = w[indx] - 1 - w[indx - 1];
w[indx - 1] = w[indx] - 1;
if(!st.count(indx - 1)) st.insert(indx - 1);
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = 1 - w[indx];
w[indx] = 1;
if(!st.count(indx)) st.insert(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
}
if (indx < n && arr[indx] <= arr[indx + 1])
{
int sum = w[indx];
int d = -w[indx];
w[indx] = 0;
if(st.count(indx)) st.erase(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
auto tp = st.upper_bound(indx);
int t = *tp;
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
w[t] += sum;
modify(1, t, sum);
if (t + 1 <= n)
modify(1, t + 1, -sum);
}
}
}
}
else
{
if (indx == 1)
{
// int t = upper_bound(w + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
w[t]--;
modify(1, t, -1);
if (t + 1 <= n)
modify(1, t + 1, 1);
int d = -w[1];
w[1] = 0;
if(st.count(1)) st.erase(1);
modify(1, 1, d);
if (2 <= n)
modify(1, 2, -d);
}
else
{
if (indx < n && arr[indx] > arr[indx + 1])
{
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
int sum = w[t];
int d = w[t] - (t - indx) - w[indx];
w[indx] = w[t] - (t - indx);
if(w[indx] == 0) st.erase(indx);
else st.insert(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = t - indx - w[t];
w[t] = t - indx;
if(w[t] == 0) st.erase(t);
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
if (indx > 1 && arr[indx - 1] > arr[indx] && !w[indx - 1])
{
auto tp = st.upper_bound(indx);
int t = * tp;
int R = w[t] - indx + 1,L = w[t] - R;
int d = L;
w[indx - 1] = L;
if(w[indx - 1]) st.insert(indx - 1);
else st.erase(indx - 1);
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
d = R - w[t];;
w[indx] = R;
if(!st.count(t)) st.insert(t);
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
if (indx > 1 && arr[indx - 1] <= arr[indx])
{
int d = w[indx - 1];
w[indx] += w[indx - 1];
if(w[indx]) st.insert(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
d = -w[indx - 1];
w[indx - 1] = 0;
if(st.count(indx - 1)) st.erase(indx - 1);
modify(1, indx - 1, d);
if (indx <= n)
modify(1, indx, -d);
}
if (indx < n && arr[indx] <= arr[indx + 1])
{
int sum = w[indx];
int d = -w[indx];
w[indx] = 0;
if(st.count(indx)) st.erase(indx);
modify(1, indx, d);
if (indx + 1 <= n)
modify(1, indx + 1, -d);
// int t = upper_bound(w + indx + 1, w + 1 + n, 0) - w;
auto tp = st.upper_bound(indx);
int t = *tp;
w[t] += sum;
d = sum;
modify(1, t, d);
if (t + 1 <= n)
modify(1, t + 1, -d);
}
}
}
// cout << "\narr :\n";
// for(int i=1;i<=n;i++) cout << arr[i] << " ";
// cout << endl;
// cout << "\nw :\n";
// for(int i=1;i<=n;i++) cout << w[i] << " ";
// cout << endl;
fun();
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
while (_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7752kb
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: 7784kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 308ms
memory: 28744kb
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: 215ms
memory: 37584kb
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: 362ms
memory: 28032kb
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: 1ms
memory: 7892kb
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: -100
Wrong Answer
time: 1ms
memory: 7696kb
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 1 1 1 1 1 1 1 1 1 1 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:
wrong answer 66th lines differ - expected: '2', found: '1'