Submission #1088381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088381		peacebringer1667	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	53 ms	11684 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;
const ll cap = 1e15;

struct CTDL{
	ll l = 0,r = 0;int val = 0;
};
vector <CTDL> vec;
int a[maxn],p = 0;

void gen(int n){
	ll cur = 0;
	
	for (int i = 1 ; i <= n ; i++){
		int cnt = 1;
		while (a[i] % 2 == 0){
			a[i] /= 2;cnt *= 2;
		}
		
		vec.push_back({cur + 1,cur + cnt,a[i]});
		cur += cnt;
		
		if (cur > cap) break;
	}
}

int solve(ll x){
	while (p < vec.size() && vec[p].r < x) p++;
	return vec[p].val;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,q;
	cin >> n;
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	gen(n);
	
	cin >> q;
	while (q--){
		ll x;
		cin >> x;
		cout << solve(x) << "\n";
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int solve(long long int)':
Main.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CTDL>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  while (p < vec.size() && vec[p].r < x) p++;
      |         ~~^~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40