11 months ago

Sahil Kumar • 260

Gurugram

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;
}

2.1 years ago

Abhishek Gupta • 30

Bhubaneswar

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;
}