제출 #1338063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338063		po_rag526	Sum Zero (RMI20_sumzero)	C++17	100 / 100	311 ms	16764 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const int mn = 4e5 + 5;
ll n, ski[mn], yipe[mn], ans[mn], pos[mn], q;
long long a[mn];
ll v[mn];
int Ql[mn], Qr[mn];


void cal(ll x){
	ski[0] = 0;
	for(int i = 1; i <= n; ++i) ski[i] = max(pos[i], ski[i - 1]);
	for(int t = 1; t <= x; ++t){
		for(int i = 1; i <= n; ++i) yipe[i] = max(yipe[i - 1], ski[i]);
		for(int i = 1; i <= n; ++i){
			if(ski[i] > 0) ski[i] = max(ski[i - 1], yipe[ski[i] - 1]);
			else ski[i]	= ski[i - 1];
		} 
	}
}

bool cmp(ll x, ll y){
	if(a[x] != a[y]) return a[x] < a[y];
	return x < y;
}

void solve(){
	cin >> n;
	a[0] = 0;
	for(int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i - 1], v[i] = i;
	v[0] = 0;
	sort(v, v + n + 1, cmp);
	pos[v[0]] = 0;
	for(int i = 1; i <= n; ++i){
		if(a[v[i]] == a[v[i - 1]]) pos[v[i]] = v[i - 1] + 1;
		else pos[v[i]] = 0;
	}
	cin >> q;
	for(int i = 1; i <= q; ++i) cin >> Ql[i] >> Qr[i];
	for(int t = 20; t >= 0; --t){
		cal(t);
//		for(int i = 1; i <= n; ++i) cout << ski[i] << " "; cout << "\n";
		for(int i = 1; i <= q; ++i){
			if(Qr[i] < Ql[i]) continue;
			if(ski[Qr[i]] >= Ql[i]) Qr[i] = ski[Qr[i]] - 1, ans[i] += (1LL << t);
		}
	}
	for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	if(fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	int testCase = 1;
	//cin >> testCase;
	while(testCase--) solve();
}

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'int main()':
sumzero.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sumzero.cpp:58:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 39 / 39