QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #733439 | #9543. Good Partitions | nnk | WA | 75ms | 7196kb | C++20 | 7.0kb | 2024-11-10 18:59:15 | 2024-11-10 18:59:15 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<iomanip>
#include<queue>
#include<math.h>
#include<map>
#include<bitset>
#include<numeric>
#include <cstring>
#include<array>
#include <string>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
//#define endl "\n"
#define mod 1000000007ll
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
#define syy return
const double pi = acos(-1.0);
using ll = long long;
using pii = pair<int, int>;
using vint = vector<int>;
using vll = vector<ll>;
using vvint = vector<vint>;
using vpo = vector<pii>;
using tup = tuple<int, int, int>;
using vbl = vector<bool>;
constexpr int N = 500005, M = 2000006;//开足够的空间 注意无向图的双向边边数*2
constexpr ll inf = 1e16;
long double eps = 1e-7;
int h[N], ans, a[104], b[104];
int flag[N];
set<int> s;
void work(int len, int op) {
for (int i = 1; i <= sqrt(len); i++) {
if (len % i == 0) {
flag[i] += op;
if (len / i != i) flag[len / i] += op;
if (op == -1) {
if (i!=1 and flag[i] == s.size() - 2) ans--;
if (len / i != i && flag[len / i] == s.size() - 2) ans--;
continue;
}
if (i!=1 and flag[i] == s.size() - 1) ans++;
if ( len / i != i && flag[len / i] == s.size() - 1) ans++;
}
}
}
void solve() {
int n, q;
cin >> n >> q;
s.clear();
ans = 1;
for (int i = 1; i <= n; i++) flag[i] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
s.insert(1);
for (int i = 2; i <= n; i++) {
if (a[i] < a[i - 1]) {
s.insert(i);
}
}
for (auto it = s.begin(); it != s.end(); it++) {
auto it2 = it;
it2++;
if (it2 == s.end()) break;
int len = *it2 - *it;
work(len, 1);
}
cout << ans << endl;
while (q--) {
int p, v;
cin >> p >> v;
if (v == a[p]) {
//ap没变
cout << ans << endl;
continue;
}
auto it = s.lower_bound(p);
auto it2 = it, it0 = it;
it2++; it0--;
bool is = 0;
if (it2 == s.end()) {
is = 1;
if (a[p] >= a[p - 1]) {
if (a[p] <= a[p + 1]) {
if (v < a[p - 1]) {
//ap是下一段起点
s.insert(p);
work(p - *it, 1);
}
if (v > a[p + 1]) {
//ap是这一段的终点
s.insert(p + 1);
work(p + 1 - *it, 1);
}
}
}
else {
if (a[p] <= a[p + 1]) {
if (v >= a[p - 1]) {
if (v <= a[p + 1]) {
//这一段和上一段合为一段
work(*it - *it0, -1);
s.erase(it);
}
if (v > a[p + 1]) {
//ap变为上一段终点
work(*it - *it0, -1);
s.erase(it);
s.insert(p + 1);
work(p + 1 - *it0, 1);
}
}
else {
if (v<a[p - 1] and v>a[p + 1]) {
//还是自己一段
}
if (v >= a[p - 1]) {
//ap变为上一段终点
work(p - *it0, -1);
s.erase(it);
}
if (v <= a[p + 1]) {
//ap变下一段起点
}
}
}
}
}
if (is == 0)
{
int len = *it2 - *it;
if (a[p] >= a[p - 1]) {
if (a[p] <= a[p + 1]) {
if (v < a[p - 1]) {
//ap是下一段起点
work(len, -1); s.insert(p);
work(p - *it, 1);
work(*it2 - p, 1);
}
if (v > a[p + 1]) {
//ap是这一段的终点
work(len, -1);s.insert(p + 1);
work(p + 1 - *it, 1);
work(*it2 - p - 1, 1);
}
}
}
else {
if (a[p] <= a[p + 1]) {
if (v >= a[p - 1]) {
if (v <= a[p + 1]) {
//这一段和上一段合为一段
work(*it - *it0, -1);
work(*it2 - *it, -1);
s.erase(it);
work(*it2 - *it0, 1);
}
if (v > a[p + 1]) {
//ap变为上一段终点
work(*it - *it0, -1);
work(*it2 - *it, -1);
s.erase(it);
s.insert(p + 1);
work(*it2 - (p + 1), 1);
work(p + 1 - *it0, 1);
}
}
}
else {
if (v<a[p - 1] and v>a[p + 1]) {
//还是自己一段
}
if (v >= a[p - 1]) {
//ap变为上一段终点
work(p - *it0, -1);
s.erase(it);
work(p + 1 - *it0, 1);
}
if (v <= a[p + 1]) {
//ap变下一段起点
auto it3 = it2; it3++;
work(*it2 - p, -1);
s.erase(it2);
work(*it3 - p, 1);
}
}
}
}
a[p] = v;
cout << ans << endl;
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5812kb
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: 5652kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 75ms
memory: 7196kb
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:
265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 265 ...
result:
wrong answer 1st lines differ - expected: '160', found: '265'