Join Us
Loading Similar Posts
Entering edit mode
Q1) Solution using binary search. For every unique value there is atmax 1 segment since sum is monotnically increasing.
//Code begins
int main() {
vector <int> v={9,3,1,2,3,9,10};
int n=v.size();
vector <int> prefix(n,0);
prefix[0]=v[0];
for (int i=1;i<n;i++) {
prefix[i]+=v[i]+prefix[i-1];
}
int ans=0;
for (int i=0;i<(n);i++) {
int sum=prefix[i];
int val=v[i];
if (binary_search(prefix.begin()+i+1,prefix.end(),val+sum) ) {
int ind=lower_bound(prefix.begin()+i+1,prefix.end(),val+sum)-prefix.begin();
if (ind<(n-1) ) {
if (v[ind+1] == (val)) {
ans++;
}
}
}
}
cout<<ans<<endl;
return 0;
}
Entering edit mode
Maxium Distinct
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
using pi = pair<int, int>;
#define srt(temp) sort(temp.begin(),temp.end())
#define srt1(temp,comp) sort(temp.begin(),temp.end(),comp)
#define f first
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b,c) for(int i=a;i<b;i+=c)
#define rev(i,a,b) for(int i=a;i>b;i--)
#define s second
int log(int x) {
return 32 - __builtin_clz(x) - 1;
//return 64 - __builtin_clzll(x) - 1;
}
const ll mod=(1e9+7);
template<class T> using min_pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vv = vector<vector<T>>;
template<class T> using v = vector<T>;
template<class T> using us = unordered_set<T>;
#define input int t;cin>>t;while(t--)
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//less-ascending
//greater -descending
//less_equal-multiset
#define ordered_set tree<ll,null_type,greater_equal<ll>,rb_tree_tag, tree_order_statistics_node_update>
//nesx:no of elements smaller than x
//eax:element at x postion
#define nesx order_of_key
#define eax find_by_order
#define sp cout << setprecision(9)
void yes(){cout<<"YES"<<endl;}
void no(){cout<<"NO"<<endl;}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
sp;
int n,k;
cin>>n;
v<int> arr1(n),arr2(n);
rep(i,0,n)cin>>arr1[i];
rep(i,0,n)cin>>arr2[i];
cin>>k;
set<pair<int,int>> st;
set<int> vis;
rep(i,0,n){
int a=arr1[i],b=arr2[i];
if(a==b)vis.insert(a);
else if(vis.find(b)!=vis.end())vis.insert(a);
else if(st.find({a,b})!=st.end())vis.insert(a);
else st.insert({a,b});
}
for(auto it:st){
int a=it.first,b=it.second;
if(vis.find(b)!=vis.end())vis.insert(a);
else{
if(vis.find(a)!=vis.end()){
vis.insert(b);
k--;
if(k==0)break;
}else{
vis.insert(a);
}
}
}
cout<<vis.size()<<endl;
}
Which college?