QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790771#9543. Good PartitionsPepinotTL 124ms14112kbC++231.6kb2024-11-28 15:17:082024-11-28 15:17:09

Judging History

你现在查看的是最新测评结果

  • [2024-11-28 15:17:09]
  • 评测
  • 测评结果:TL
  • 用时:124ms
  • 内存:14112kb
  • [2024-11-28 15:17:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
using pii=pair<int,int>;
const int mod=998244353;

int n;
set<int> st;

int ope() {
    if(st.empty()) return n;

    int w=*st.begin();

    for(auto i:st) {
        w=__gcd(w,i);
        if(w==1) break;
    }

    map<int,int> mp;
    for(int i=2;w!=1;i++) {
        while(w%i==0) {
            w/=i;
            mp[i]++;
        }
    }

    int cnt=1;
    for(auto [x,y]:mp)
        cnt*=y+1;

    return cnt;
}

void solve() {
    int q;
    cin>>n>>q;
    vector<int> v(n+2);
    v[0]=2e9+1,v[n+1]=0;
    for(int i=1; i<=n; i++) cin>>v[i];

    // vector<int> bad;
    st.clear();
    for(int i=1; i<n; i++) {
        if(v[i]>v[i+1]) {
            // bad.push_back(i);
            st.insert(i);
        }
    }

    // int cnt_bad=0;
    // for(int i=0; i<bad.size()-1; i++)
    //     if(bad[i+1]-bad[i]==1) cnt_bad++;

    cout<<ope()<<endl;

    while(q--) {
        int a,b; cin>>a>>b;

        //多了一个
        if(v[a-1]<=v[a]&&v[a-1]>b) {
            st.insert(a-1);
        }
        if(v[a]<=v[a+1]&&b>v[a+1]) {
            st.insert(a);
        }

        //少了一个
        if(v[a-1]>v[a]&&v[a-1]<=b) {
            st.erase(a-1);
        }
        if(v[a]>v[a+1]&&b<=v[a+1]) {
            st.erase(a);
        }

        v[a]=b;

        cout<<ope()<<endl;

    }
}

signed main() {
    ios::sync_with_stdio(false),cin.tie(nullptr);

    int t; cin>>t;
    while(t--)
        solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

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: 0ms
memory: 3616kb

input:

1
1 1
2000000000
1 1999999999

output:

1
1

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 88ms
memory: 4612kb

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: 124ms
memory: 14112kb

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: -100
Time Limit Exceeded

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: