# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1209977 | anfi | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include "molecules.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using int64 = long long;
#define pi pair<int64, int64>
#define artefak pair<pi, pi>
const int64 inf = -(1LL << 40);
const int64 mxn = (1 << 18);
int64 parent[4*mxn],sz[4*mxn],val[mxn*4][2],mx[mxn*4];
int64 find(int n){
return parent[n] == n ? n : parent[n] = find(parent[n]);
}
int64 hitung(int n){
if(sz[n]%2 == 0) return 0;
return max(val[n][n&1], mx[n]);
}
vector<int64> find_subset(int l, int u, vector<int64> &a){
int64 n = a.size();
vector<pair<int64,int64>> wawi;
for(int i = 0; i < n; i++) wawi.push_back({a[i], i});
int64 ll = 0, rr = 0,sum = 0;
while(ll < n){
while(rr < n && sum < l) sum += wawi[rr++].fi;
if(l <= sum && sum <= u){
vector<int64> ans;
for(int i = ll; i < rr; i++) ans.push_back(wawi[i].se);
return ans;
}
sum -= wawi[ll++].fi;
if(l <= sum && sum <= u){
vector<int64> ans;
for(int i = ll; i < rr; i++) ans.push_back(wawi[i].se);
return ans;
}
}
return vector<int>(0);
}