QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#727347 | #9543. Good Partitions | ssx# | WA | 128ms | 12304kb | C++20 | 2.0kb | 2024-11-09 12:52:56 | 2024-11-09 12:52:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 7;
const int N = 2e5 + 50;
ll n, m, tr[N * 4]; // gcd
ll a[N];
ll gcd(ll a,ll b){
if(a==0){
return b;
}
return b?gcd(b,a%b):a;
}
void pushup(ll u)
{
tr[u] = gcd(tr[u * 2], tr[u * 2 + 1]);
}
void modify(ll u, ll l, ll r, ll v, ll k)
{
if (l == r)
{
//cout<<l<<" "<<k<<endl;
if (k == 0) tr[u] = 0;
else tr[u] = l;
}
else
{
ll mid = (l + r) >> 1;
if (v <= mid) modify(u * 2, l, mid, v, k);
else modify(u * 2 + 1, mid + 1, r, v, k);
pushup(u);
}
}
int ys[N];
void solve()
{
ll q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= 4 * n + 10; i++) tr[i] = 0;
//cout<<gcd(0,100)<<endl;
for(int i=2;i<=n;i++){
if(a[i]<a[i-1]){
modify(1,0,200005,i-1,1);
}
}
// modify(1,0,200005,2,1);
// modify(1,0,200005,4,1);
ll ans=tr[1];
if(ans==0){
cout<<n<<endl;
}else{
cout<<ys[ans]<<endl;
}
int x=0,y=0;
for(int i=0;i<q;i++){
cin>>x>>y;
a[x]=y;
if(x!=1 && a[x]<a[x-1]){
modify(1,0,200005,x-1,1);
}
else{
modify(1,0,200005,x-1,0);
}
if(x!=n && a[x+1]<a[x]){
modify(1,0,200005,x,1);
}
else{
modify(1,0,200005,x,0);
}
ans=tr[1];
//cout<<ans<<endl;
if(ans==0){
cout<<n<<endl;
}else{
cout<<ys[ans]<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll T = 1;
cin >> T;
for(int i=1;i<=200000;i++){
for(int j=0;i*j<200000;j++){
ys[i*j]++;
}
}
while (T --)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 8476kb
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: 8508kb
input:
1 1 1 2000000000 1 1999999999
output:
1 1
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 89ms
memory: 12224kb
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: 128ms
memory: 12304kb
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: 116ms
memory: 12180kb
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: 3ms
memory: 8416kb
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: 3ms
memory: 8456kb
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 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 2 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
wrong answer 17th lines differ - expected: '2', found: '1'