제출 #1330653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1330653		herominhsteve	Sum Zero (RMI20_sumzero)	C++20	61 / 100	394 ms	84020 KiB

sumzero

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "SUMZERO"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int INF = (long long) 1e9 + 15092007;
const int LOG = 19;

int n,q;
vector<int> a;

void init(){
	cin>>n;
	a.resize(n); for (int &x : a) cin>>x;
	cin>>q;
}

void sol(){
	vector<long long> pre(n + 1, 0);
	for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];

	// ? sum[l,r)
	function<long long(int,int)> calSum = [&] (int l,int r) -> long long {
		return pre[r] - pre[l];
	};

	// ? 0...n
	vector<long long> nxtSame(n + 1, INF);
	unordered_map<long long,int> lastOccur;
	
	for (int pos = n; pos >= 0; pos--){
		unordered_map<long long,int>::iterator it = lastOccur.find(pre[pos]);
		nxtSame[pos] = (it == lastOccur.end() ? INF : it->second);
		lastOccur[pre[pos]] = pos;
	}

	// * nxtStart[i]: earliest r >= i that sum(i...r) = 0 (= nxtSame[i - 1])
	vector<int> nxtStart(n + 2, INF);
	for (int i = 1; i <= n; i++){
		nxtStart[i] = nxtSame[i - 1];
	}

	vector<int> bestEnd(n + 3, INF);
	for (int i = n; i >= 1; i--){
		bestEnd[i] = min(nxtStart[i], bestEnd[i + 1]);	
	}
	
	vector<vector<int>> up(LOG + 1, vector<int>(n + 2, n + 1));
	vector<vector<int>> endUp(LOG + 1, vector<int>(n + 2, INF));

	for (int i = 1; i <= n; i++){
		endUp[0][i] = bestEnd[i];
		up[0][i] = (bestEnd[i] >= INF ? n + 1 : min(n + 1, bestEnd[i] + 1));
	}

	for (int k = 1; k <= LOG; k++){
		for (int i = 1; i <= n; i++){
			if (up[k - 1][i] <= n + 1){
				up[k][i] = up[k - 1][up[k - 1][i]];
				endUp[k][i] = endUp[k - 1][up[k - 1][i]];
			}
		}
	}

	while (q--){
		int L,R; cin>>L>>R;
		int pos = L;
		long long res = 0;
		for (int k = LOG; k >= 0; k--){
			if (pos <= n and endUp[k][pos] <= R){
				res += (1ll << k);
				pos = up[k][pos];
			}
		}
		cout<<res<<el;
	}

}

int main(){
	setup();
	init();
	sol();
}

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

sumzero.cpp: In function 'void setup()':
sumzero.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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