# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
859144 | mircea_007 | Sum Zero (RMI20_sumzero) | C++17 | 262 ms | 22100 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <algorithm>
#include <vector>
using ll = long long;
const int MAXN = 4e5;
const int MAXQ = 4e5;
const int INF = 1e9;
struct Range {
int st, dr;
} ranges[1 + MAXN];
int nranges;
int next[MAXN];
int jump[MAXN];
int depth[MAXN];
std::pair<ll, int> sp[1 + MAXN]; // { sp, idx }
// primul i astfel incat ranges[i].st >= x
int next_after( int x ){
int st = -1, dr = nranges, mij; // ranges[nranges] e santinela
while( dr - st > 1 ){
mij = (st + dr) >> 1;
if( ranges[mij].st >= x )
dr = mij;
else
st = mij;
}
return dr;
}
int query( int qst, int qdr ){
int u = next_after( qst );
int lowest = depth[u];
while( ranges[u].dr <= qdr ){
if( ranges[jump[u]].dr <= qdr )
u = jump[u];
else
u = next[u];
}
return lowest - depth[u];
}
int main(){
int n;
scanf( "%d", &n );
sp[0] = { 0, 0 };
for( int i = 0 ; i < n ; i++ ){
scanf( "%lld", &sp[i + 1].first );
sp[i + 1].first += sp[i].first;
sp[i + 1].second = i + 1;
}
std::sort( sp, sp + n + 1 );
nranges = 0; // global pentru next_after()
for( int i = 1 ; i < n + 1 ; i++ )
if( sp[i - 1].first == sp[i].first )
ranges[nranges++] = Range{ sp[i - 1].second, sp[i].second - 1 };
std::sort( ranges, ranges + nranges, []( const Range &a, const Range &b ) -> bool {
return a.st < b.st; // nu se intampla ca a.st == b.st
} );
int smallest_dr = INF;
for( int i = nranges ; i-- ; ){ // mark bad intervals
if( ranges[i].dr > smallest_dr )
ranges[i] = Range{ INF, INF };
else
smallest_dr = ranges[i].dr;
}
// remove marked intervals
nranges = std::remove_if( ranges, ranges + nranges, []( const Range &a ) -> bool {
return a.st == INF;
} ) - ranges;
ranges[nranges] = Range{ INF, INF };
next[nranges] = jump[nranges] = nranges;
depth[nranges] = 0;
// binary lifting
for( int i = nranges ; i-- ; ){
int p = next_after( ranges[i].dr + 1 );
next[i] = p;
depth[i] = 1 + depth[p];
if( depth[p] - depth[jump[p]] == depth[jump[p]] - depth[jump[jump[p]]] )
jump[i] = jump[jump[p]];
else
jump[i] = p;
}
int q;
for( scanf( "%d", &q ) ; q-- ; ){
int qst, qdr;
scanf( "%d%d", &qst, &qdr );
qst--;
qdr--;
printf( "%d\n", query( qst, qdr ) );
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |