Recently, I tried to solve the problem: Meteors
It is a well-known problem that is usually solved using Parallel Binary Search.
However, before learning about that technique, I attempted to solve it in my own way. Surprisingly, my solution somehow passed within the time limit, even though I expected it to get TLE based on my complexity estimation.
MY CODE#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
#define memo(a,b) memset(a,b,sizeof(a))
const ll N=3e5+5;
vector<pair<ll,ll>> t[2 * N];
ll sz;
vector<ll> node;
void crn_node(ll p) {
for (p += sz; p >= 1; p >>= 1)
if (!t[p].empty()) node.push_back(p);
}
void input(ll l, ll r, ll val, ll id) { // range [l, r) so r is r+1
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1)
{
ll pre=0;
if(t[l].size())pre=t[l][t[l].size()-1].second;
t[l++].push_back({id,val+pre});
}
if (r & 1)
{
--r;
ll pre=0;
if(t[r].size())pre=t[r][t[r].size()-1].second;
t[r].push_back({id,val+pre});
}
}
}
int main ()
{
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,m; cin>>n>>m;
sz=m+1; // sz is the size if seg and seg is 1 base by ignoring 0
vector<ll>val[n+1];
for(ll i=1;i<=m;i++){ll x; cin>>x; val[x].push_back(i);}
ll need[n+1];
for(ll i=1;i<=n;i++)cin>>need[i];
ll q; cin>>q; // I named k as q from problem
for(ll i=1;i<=q;i++)
{
ll l,r;cin>>l>>r;
ll qv;cin>>qv;
if(l>r){ input(l,sz,qv,i); input(1,r+1,qv,i);}
else input(l,r+1,qv,i);
}
// This is the part Im confused about
for(ll i=1;i<=n;i++)
{
for(auto v:val[i])crn_node(v);
ll s=1; ll e=q; ll ans=-1;
while(s<=e)
{
ll mid=s+(e-s)/2;
ll sum=0;
for(auto v:node)
{
auto it = upper_bound(t[v].begin(), t[v].end(), make_pair(mid,LLONG_MAX));
if(it!=t[v].begin())
{
--it;
sum+=it->second;
if(sum>=need[i])break;
}
}
if(sum>=need[i]){ ans=mid;e=mid-1;}
else s=mid+1;
}
node.clear();
if(ans==-1)cout<<"NIE"<<endl;
else cout<<ans<<endl;
}
}
At first, I estimated my code’s complexity as: (n + m) * log(m) * log(q)^2
The part that confuses me is the binary search: inside it, I loop over a node vector of size roughly log(m). At the same time, the total size of all vectors could be around q * log(m), as far as I understand.
Does the segment tree structure somehow reduce the number of iterations or the effective number of values processed, or am I misunderstanding the actual complexity?
For context, the input function is implemented as an iterative segment tree. Each query stores a prefix sum over a range, and the crn_node function is used to collect all the relevant node indices along the path for a given position p.
To my understanding, I would have needed to remove at least one or more log factors from the complexity just to pass the time limits.
If there’s some good reason why it passed, then this kind of trick could be really useful for other problems as well. I’d love to understand it properly and learn how and why. Any insights or guidance would be greatly appreciated:)
update: [ I don’t really care whether people upvote or downvote, I just want to understand the reason. I’ll most probably delete the blog after I get the answer. If anyone know why it passed, please let me know. I’ve even asked several AIs about this, but none of them gave a convincing explanation. Most of the time they just hallucinated answers, and when I tried to argue with the reasoning, the explanation kept changing every time, which made it even more confused ]
