QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721442 | #9543. Good Partitions | wkr | ML | 0ms | 5980kb | C++20 | 2.4kb | 2024-11-07 16:07:11 | 2024-11-07 16:07:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int n, m;
const int N = 2e5 + 10;
int a[N], phi[N], b[N];
inline int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
struct SEG
{
#define lson id << 1
#define rson id << 1 | 1
int sum;
} seg[N << 2];
inline void up(int id)
{
seg[id].sum = gcd(seg[lson].sum, seg[rson].sum);
}
inline void build(int id, int l, int r)
{
if (l == r)
{
if (b[l] >= 0)
{
seg[id].sum = 0;
}
else
{
seg[id].sum = l;
}
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
up(id);
}
inline void change(int id, int l, int r, int pos, int val)
{
if (l == r)
{
if(val>=0)
{
seg[id].sum = 0;
}
else
{
seg[id].sum = l;
}
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
{
change(lson, l, mid, pos, val);
}
else
{
change(rson, mid + 1, r, pos, val);
}
up(id);
}
inline void solved()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i < n; i++)
{
b[i] = a[i + 1] - a[i];
}
build(1, 1, n - 1);
int v = abs(seg[1].sum);
if (n == 1 || v == 0)
{
cout << n << endl;
}
else
{
cout << phi[v] << endl;
}
for (int i = 1; i <= m; i++)
{
int pos, v;
cin >> pos >> v;
a[pos] = v;
if (pos > 1)
{
change(1, 1, n - 1, pos - 1, a[pos] - a[pos - 1]);
}
if (pos < n)
{
change(1, 1, n - 1, pos, a[pos + 1] - a[pos]);
}
if (n == 1)
{
cout << n << endl;
continue;
}
v = abs(seg[1].sum);
if (v == 0)
{
cout << n << endl;
}
else
{
cout << phi[v] << endl;
}
}
}
int main()
{
close;
for (int i = 1; i <= N - 2; i++)
{
for (int j = 1; j * i <= N - 2; j++)
{
phi[j * i]++;
}
}
int T;
cin >> T;
while (T--)
solved();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5980kb
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
Memory Limit Exceeded
input:
1 1 1 2000000000 1 1999999999