975C - Valhalla Siege - CodeForces Solution


binary search *1400

Please click on ads to support us..

Python Code:

import bisect
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, q = map(int, input().split())
a = list(map(int, input().split()))
k = list(map(int, input().split()))
s = [0]
for i in a:
    s.append(s[-1] + i)
ans = []
u = 0
for i in k:
    u += i
    x = bisect.bisect_right(s, u)
    ans0 = n - x + 1
    if not ans0:
        ans0, u = n, 0
    ans.append(ans0)
sys.stdout.write("\n".join(map(str, ans)))

C++ Code:

#include<bits/stdc++.h>
using namespace std;
using ll = long long int ;
int upperbound(long long int x, vector<long long int > & cum) {
	int low = 0 , high = (int)cum.size() ;
	
	while(low < high){
		int mid = (low + high ) >> 1;
		if( x >= cum[mid] ) low = mid + 1;
		else high = mid ;
	}
	return low ;
}
 
 
int main()
{
	int n , q ;
	scanf("%d%d",&n,&q);
	
	vector<int> strength(n);
	vector<long long int > arrows(q),cum(n+1);
 
	
	for(auto &x : strength ) scanf("%d",&x);
	for(auto &x : arrows ) scanf("%lld",&x);
	
	for(int i = 1 ; i <= n; i++){
		cum[i] = cum[i-1] + strength[i-1] ;
	}
 
	ll last = 0;
	for(long long int x : arrows){
		x += last ;
		
		int ind = upperbound(x,cum);
		if(ind > n ){
			last = 0;
			printf("%d\n",n);
			continue ;
		}
		ll alive = n - ind + 1;
		last = x ;

		printf("%lld\n",alive) ;
	
	}
 
    return 0;
}


Comments

Submit
0 Comments
More Questions

281A - Word Capitalization
1646A - Square Counting
266A - Stones on the Table
61A - Ultra-Fast Mathematician
148A - Insomnia cure
1650A - Deletions of Two Adjacent Letters
1512A - Spy Detected
282A - Bit++
69A - Young Physicist
1651A - Playoff
734A - Anton and Danik
1300B - Assigning to Classes
1647A - Madoka and Math Dad
710A - King Moves
1131A - Sea Battle
118A - String Task
236A - Boy or Girl
271A - Beautiful Year
520B - Two Buttons
231A - Team
479C - Exams
1030A - In Search of an Easy Problem
158A - Next Round
71A - Way Too Long Words
160A - Twins
1A - Theatre Square
1614B - Divan and a New Project
791A - Bear and Big Brother
1452A - Robot Program
344A - Magnets