Submission #377168

#	Time	Username	Problem	Language	Result	Execution time	Memory
377168		jamielim	Bigger segments (IZhO19_segments)	C++14	100 / 100	94 ms	24188 KiB

segments

    #include <bits/stdc++.h>
    using namespace std;
     
    #define fi first
    #define se second
    #define mp make_pair
    #define pb emplace_back
    #define ALL(x) x.begin(),x.end()
    #define SZ(x) (int)x.size()
    typedef long long ll;
    typedef pair<int,int> ii;
    typedef pair<ii,ii> i4;
    const int MOD=1000000007;
    const int INF=1012345678;
    const ll LLINF=1012345678012345678LL;
    const double PI=3.1415926536;
    const double EPS=1e-14;
     
    int n;
    ll arr[500005];
    ll pre[500005];
    ll sz[500005];
    int ans[500005];
     
    int main(){
    	scanf("%d",&n);
    	for(int i=0;i<n;i++){
    		scanf("%lld",&arr[i]);
    		if(i==0)pre[0]=arr[0];
    		else pre[i]=pre[i-1]+arr[i];
    	}
    	deque<pair<ll,int> > q;
    	sz[0]=arr[0];ans[0]=1;
    	q.pb(sz[0]+pre[0],0);
    	for(int i=1;i<n;i++){
    		sz[i]=sz[i-1]+arr[i];
    		ans[i]=ans[i-1];
    		while(!q.empty()&&q.front().fi<=pre[i]){
    			sz[i]=pre[i]-pre[q.front().se];
    			ans[i]=ans[q.front().se]+1;
    			q.pop_front();
    		}
    		while(!q.empty()&&q.back().fi>=sz[i]+pre[i])q.pop_back();
    		q.pb(sz[i]+pre[i],i);
    	}
    	printf("%d",ans[n-1]);
    }
    // sz[j]<=pre[i]-pre[j] -> sz[j]+pre[j]<=pre[i]

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:26:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |      scanf("%d",&n);
      |      ~~~~~^~~~~~~~~
segments.cpp:28:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |       scanf("%lld",&arr[i]);
      |       ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27