fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define el '\n'
  4. #define Ramadan ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. using namespace std;
  6. int bits[(int)2e5+5][33]{};
  7. int pre[(int)2e5+5][33];
  8. int main()
  9. {
  10.     Ramadan
  11.     int t = 1;
  12.     cin >> t;
  13.     while (t--) {
  14.             int n; cin >> n;
  15.             vector<ll> pre(n+1,0);
  16.             for(int i = 1; i <= n; i++)
  17.             {
  18.                 int x; cin >> x;
  19.                 pre[i] = pre[i-1]+x;
  20.             }
  21.             int q; cin >> q;
  22.             while(q--)
  23.             {
  24.                 ll l,u,ans; cin >> l >> u;
  25.                 auto it = lower_bound(pre.begin(),pre.end(),u+pre[l-1]);
  26.                 //cout << *it << el;
  27.  
  28.                 if(*it == pre[l])
  29.                 {
  30.                     ans = l;
  31.                 }
  32.                 else if(it == pre.end())
  33.                 {
  34.                     ans = n;
  35.                 }
  36.                 else
  37.                 {
  38.  
  39.                     ll sum;
  40.                     if(u >= u-(*it-pre[l-1]))
  41.                     sum = u-(*it-pre[l-1]);
  42.                     else
  43.                     sum = (*it-pre[l-1])-u-1;
  44.                     ll cur1 = u*(u+1)/2-sum*(sum+1)/2;
  45.                     ll cur2 = -1e18;
  46.                     it--;
  47.                     if(u >= u-(*it-pre[l-1]))
  48.                     sum = u-(*it-pre[l-1]);
  49.                     else
  50.                     sum = (*it-pre[l-1])-u-1;
  51.  
  52.                     cur2 = u*(u+1)/2-sum*(sum+1)/2;
  53.                     //cout << it-pre.begin() << ' ' << it-pre.begin()+1 << el;
  54.                     if(cur2 >= cur1) ans = it-pre.begin();
  55.                     else ans = it-pre.begin()+1;
  56.                     //ans = it-pre.begin();
  57.                 }
  58.                 cout << ans << ' ';
  59.             }
  60.             cout << el;
  61.     }
  62. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/Wog6YB
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
9 days ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!