QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726234 | #9543. Good Partitions | the_fool | WA | 53ms | 6664kb | C++20 | 2.9kb | 2024-11-08 22:29:04 | 2024-11-08 22:29:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define ls (u << 1)
#define rs (u << 1 | 1)
struct segtree {
int n, p;
vector<int> g;
segtree (int _n) {
n = _n;
p = __bit_ceil(n + 2);
g.assign(2 * p + 1, {});
}
void pushup(int u) {
// cerr << "PUSHUP " << u << "\n";
// cerr << format("g[{}] = gcd(g[{}] = {}, g[{}] = {}) = {}", u, ls, g[ls], rs, g[rs], gcd(g[ls], g[rs])) << "\n";
g[u] = gcd(g[ls], g[rs]);
}
void cg(int u, int v) {
// assert(u >= 1 and u <= n);
// int uu = u;
u += p;
if (v > int(1E9)) {
v = 0;
}
g[u] = v;
while (u >>= 1) {
pushup(u);
}
// cerr << "AFTER CG " << uu << " " << v << "\n";
// show();
// cerr << "\n";
}
// void show() {
// cerr << "NOW ALL THE BASE:\n";
// for (int i = 1; i <= n; i++) {
// cerr << g[i + p] << " \n"[i == n];
// }
// cerr << "NOW ALL THE TREE:\n";
// for (int i = 1; i <= 2 * p; i++) {
// cerr << g[i] << " \n"[i == 2 * p];
// }
// }
};
#undef ls
#undef rs
constexpr int inf = 2E9 + 10;
constexpr int N = 2E5 + 10;
int cnt[N];
int init = []() {
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
cnt[j]++;
}
}
return 0;
}();
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a.emplace_back(inf);
set<int> s{0, inf};
for (int i = 1; i <= n; i++) {
if (a[i] > a[i + 1]) s.emplace(i);
}
segtree tr(n + 1);
int ls = 0;
for (int x : s) {
if (x) {
tr.cg(ls + 1, x - ls);
ls = x;
}
}
auto del = [&](int x) {
auto it = s.find(x);
if (it == s.end()) return;
auto it1 = prev(it), it2 = next(it);
tr.cg(x + 1, 0);
tr.cg(*it1 + 1, *it2 - *it1);
s.erase(it);
};
auto add = [&](int x) {
auto it1 = s.lower_bound(x);
if (*it1 == x) return;
auto it2 = prev(it1);
tr.cg(*it2 + 1, x - *it2);
tr.cg(x + 1, *it1 - x);
s.emplace(x);
};
cout << cnt[tr.g[1] == 0 ? n : tr.g[1]] << "\n";
while (q--) {
int x, v;
cin >> x >> v;
del(x);
del(x - 1);
a[x] = v;
if (a[x] > a[x + 1]) add(x);
if (a[x - 1] > a[x]) add(x - 1);
int res = tr.g[1];
if (res == 0) res = n;
cout << cnt[res] << "\n";
// tr.show();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 4588kb
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: 3ms
memory: 4556kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 53ms
memory: 6664kb
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 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42 160 42...
result:
wrong answer 2nd lines differ - expected: '200000', found: '42'