Submission #1177914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177914		ezzzay	Separator (CEOI19_separator)	C++20	90 / 100	1245 ms	75352 KiB

separator

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=2e6+5;
const int P=1e9;
int a[N];
vector<int>ans;
signed main(){
    int n;
    cin>>n;
    int s=0;
    set<int>st;
    int mx=0;
    for(int i=1;i<=n;i++){
        int b;
        cin>>b;
        a[i]=(s+b)%P;
        vector<int>del;
        auto it=st.upper_bound( a[i] *P+i);
        while(it!=st.end()){
            del.pb(*it);
            it++;
        }
        for(auto h:del){
            st.erase(h);
        }
        if(a[i]>=mx){
            st.insert(a[i]*P+i);
        }
        mx=max(mx,a[i]);
        s=st.size();
        ans.pb(s);
    }
    
    for(auto s:ans)cout<<s<<endl;
    
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 0 / 10