oj.uz

Submission #942677

# Submission time Handle Problem Language Result Execution time Memory
942677 2024-03-11T02:48:37 Z thunopro Sum Zero (RMI20_sumzero) C++14
100 / 100
 907 ms 16164 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 400009 
#define ll long long 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()
#define TIME 1.0*clock()/CLOCKS_PER_SEC

const int mod = 1e9+7; 
const int INF = 1e9; 

typedef vector<int> vi; 
typedef pair<int,int> pii;
typedef vector<pii> vii;  
typedef vector<ll> vl;

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a > mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

template <typename T> void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template <typename T> void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ;
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}

const int LOG = 2 ; 
int n , nq ; 
int a [maxn] ; 

int L [maxn][3] ; 

const int B = 7 ; 

void build () 
{
	ll sum = 0 ; 
	unordered_map <ll,int> mp ; 
	mp [0] = n+1 ; 
	memset ( L , 0x3f , sizeof L ) ; 
	for ( int i = n ; i >= 1 ; i -- ) 
	{
		sum += a [i] ; 
		if ( mp [sum] ) L [i][0] = mp [sum] - 1 ; 
		chkmin (L[i][0],L[i+1][0]) ; 
		mp [sum] = i ;
	}
	for ( int j = 1 ; j <= LOG ; j ++ ) 
	{
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			if ( L[i][j-1] <= n ) L [i][j] = L [i][j-1] ; 
			else
			{
				L [i][j] = INF ; 
				continue ; 
			}
			for ( int t = 1 ; t < (1<<B) ; t ++ )
			{
				if ( L [i][j] <= n ) L [i][j] = L [L[i][j]+1][j-1] ; 
				else 
				{
					L [i][j] = INF ; break ; 
				}
			}
		}
	}
}
int main () 
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0);cout.tie(0);
//	rf () ; 
	
	cin >> n ; 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i] ; 
	
	build () ; 
	
	cin >> nq ; 
	while ( nq -- ) 
	{
		int l , r ; cin >> l >> r ;
		int res = 0 ; 
		for ( int j = LOG ; j >= 0 ; j -- ) 
		{
			while ( L [l][j] <= r ) 
			{
				res += 1<<(B*j) ; 
				l = L [l][j]+1 ; 
			}
		}
		cout << res << "\n" ; 
	}
}

Compilation message

sumzero.cpp: In function 'void rf()':
sumzero.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5212 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 5 ms 5208 KB Output is correct
4 Correct 5 ms 5212 KB Output is correct
5 Correct 5 ms 5208 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5212 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 5 ms 5208 KB Output is correct
4 Correct 5 ms 5212 KB Output is correct
5 Correct 5 ms 5208 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 152 ms 7092 KB Output is correct
8 Correct 91 ms 7860 KB Output is correct
9 Correct 140 ms 6196 KB Output is correct
10 Correct 153 ms 7092 KB Output is correct
11 Correct 92 ms 6960 KB Output is correct
12 Correct 146 ms 6308 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5212 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 5 ms 5208 KB Output is correct
4 Correct 5 ms 5212 KB Output is correct
5 Correct 5 ms 5208 KB Output is correct
6 Correct 6 ms 5212 KB Output is correct
7 Correct 152 ms 7092 KB Output is correct
8 Correct 91 ms 7860 KB Output is correct
9 Correct 140 ms 6196 KB Output is correct
10 Correct 153 ms 7092 KB Output is correct
11 Correct 92 ms 6960 KB Output is correct
12 Correct 146 ms 6308 KB Output is correct
13 Correct 813 ms 13604 KB Output is correct
14 Correct 515 ms 16164 KB Output is correct
15 Correct 899 ms 9412 KB Output is correct
16 Correct 789 ms 16068 KB Output is correct
17 Correct 588 ms 12956 KB Output is correct
18 Correct 907 ms 9432 KB Output is correct