Submission #1172997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172997		coolboy19521	Bigger segments (IZhO19_segments)	C++17	100 / 100	45 ms	14232 KiB

segments

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")

#include "bits/stdc++.h"

#define mxN 500005
#define bfS 1<<15

using namespace std;

long long pr[mxN];
int a[mxN];

inline namespace putin{
	char buf[bfS];
	int pos, len;
	char nextChar(){
		if (pos == len){
			len = fread(buf, 1, bfS, stdin), pos = 0;
			if (!len) return EOF;
		}
		return buf[pos ++];
	}
	int nextInt(){
		int s = 1, x = 1;
		char c;
		while (!isdigit(c = nextChar()))
			if ('-' == c) x = -1;
		x *= c - '0';
		while (isdigit(c = nextChar()))
			x = x * 10 + c - '0';
		return x;
	}
}

inline namespace putout{
	char buf[bfS];
	char nmb[6];
	int pos;
	void flushOut(){
		fwrite(buf, 1, pos, stdout);
		pos = 0;
	}
	void writeChar(char c){
		if (pos == bfS)
			flushOut();
		buf[pos ++] = c;
	}
	void writeInt(int x){
		if (x < 0){
			writeChar('-');
			x *= -1;
		}
		int len = 0;
		for (; x >= 10; x /= 10)
			nmb[len ++] = '0' + x % 10;
		writeChar('0' + x);
		while (len)
			writeChar(nmb[-- len]);
		writeChar('\n');
	}
	void initOutput(){
		assert(!atexit(flushOut));
	}
}

int main(){
	initOutput();

	int N;
	cin >> N;
	
	for (int i = 1; i <= N; i ++)
		a[i] = nextInt();

	priority_queue<tuple<long long,int,int>> pq;
	
	long long aux = 0;
	int ans = 0;

    pair<int,int> bs = {0, 0};
	
	for (int i = 1; i <= N; i ++){
		pr[i] = aux += a[i];

		for(;;){
			if (pq.empty()) break;
			auto [sm, cn, ix] = pq.top();
			
			sm = -sm;
			
			if (sm - aux <= 0){
                bs = max(bs, {cn, ix});
				pq.pop();
			}
			else break;
		}
		
		auto [cn, ix] = bs;
        ans = cn + 1;
		
		pq.emplace(pr[ix] - pr[i] - aux, cn + 1, i);
	}

	writeInt(ans);	
}

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