Submission #234831

#	Time	Username	Problem	Language	Result	Execution time	Memory
234831		Lyestria	Separator (CEOI19_separator)	C++14	100 / 100	300 ms	30048 KiB

separator

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll>pll;
typedef __int128 lll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod=1e9+7;
const ll mn=1e6+10;
ll a[mn];
bool gud[mn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int ans=0;
    stack<int>s;
    int ma=-1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=ans,a[i]%=(int)1e9;
        if(a[i]>ma)gud[i]=1;
        ma=max(ma,(int)a[i]);
        while(s.size()&&a[i]<=a[s.top()]){
            gud[i]=0;
            ans-=gud[s.top()];
            s.pop();
        }
        s.push(i),ans+=gud[i];
        printf("%d\n",ans);
    }
}

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