Question: Sprinklr OA | Tutoring Dilemma | Robot Run | Splitting Edges | IIIT Allahabad | 1st August 2023
0
Entering edit mode

ADD COMMENTlink 15 months ago PoGo 2.4k
2
Entering edit mode

// tutoring dilemma

// using segment tree but pbds(policy based data structure) can also be used

 
 
 
 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define M 1000000007
#define fo(i, l, r) for(i=l;l<r?i<r:i>r;l<r?i++:i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
 
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<int>     vi;
typedef vector<ll>      vl;
typedef vector<vi>      vvi;
typedef vector<vl>      vvl;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;
 
ll segtree[2000008];
 
int update(int l, int r, int up_idx, int val, int idx) {
    if(up_idx<l || up_idx>r) return segtree[idx];
 
    if(l==r) return segtree[idx]=val;
 
    int mid=l+(r-l)/2;
 
    return segtree[idx]=update(l, mid, up_idx, val, idx*2)+update(mid+1, r, up_idx, val, idx*2+1);
}
 
ll fetch(int l, int r, int cl, int cr, int idx) {
    if(cl>r || cr<l) return 0;
 
    int mid=l+(r-l)/2;
 
    if(cl<=l && r<=cr) return segtree[idx];
 
    return fetch(l, mid, cl, cr, idx*2)+fetch(mid+1, r, cl, cr, idx*2+1);
}
 
int main() {
   
    int n;cin >> n;
    vector<vector<int>> v1,v2;
    for(int i=0;i<n;i++) {
        int a,b;cin >> a >> b;
        v1.pb({a,b});
    }
    for(int i=0;i<n;i++) {
        int a,b;cin >> a >> b;
        v2.pb({a,b});
    }
 
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    int freq[400008];
    memset(segtree, 0, sizeof(segtree));
    memset(freq, 0, sizeof(freq));
 
    vector<int> tempv;
 
    for(auto var:v1) tempv.pb(var[1]);
    for(auto var:v2) tempv.pb(var[1]);
 
    sort(tempv.begin(), tempv.end());
 
    int i=0,j=0,count=1;
    map<int,int> mp;
 
    while(i<tempv.size()) {
        int curr=tempv[i];
        while(i<tempv.size() && tempv[i]==curr) i++;
        mp[curr]=count;
        count++;
    }
 
    ll ans=0;
    i=0,j=0;
    while(j<n) {
        while(i<n && v1[i][0]<v2[j][0]) {
            freq[mp[v1[i][1]]]++;
            update(1, 2*n+1, mp[v1[i][1]], freq[mp[v1[i][1]]], 1);
            i++;
        }
       
        if(mp[v2[j][1]]!=1) {
            ans+=fetch(1, 2*n+1, 1, mp[v2[j][1]]-1, 1);
        }
        j++;
    }
   
    cout << ans << "\n";
 
    return 0;
}
ADD COMMENTlink 15 months ago sumeet kumar sahoo • 290
Entering edit mode
0

Could you please share the code of PBDS too or share the approach, for this question.

ADD REPLYlink 13 months ago
Xavior
• 0
0
Entering edit mode
// //using segment tree but pbds(policy based data structure) can also be used #includeusing namespace std; #define ll long long #define M 1000000007 #define fo(i, l, r) for(i=l;lr;lpii; typedef pairpll; typedef vectorvi; typedef vectorvl; typedef vectorvvi; typedef vectorvvl; typedef vectorvpii; typedef vectorvpll; ll segtree[2000008]; int update(int l, int r, int up_idx, int val, int idx) { if(up_idxr) return segtree[idx]; if(l==r) return segtree[idx]=val; int mid=l+(r-l)/2; return segtree[idx]=update(l, mid, up_idx, val, idx*2)+update(mid+1, r, up_idx, val, idx*2+1); } ll fetch(int l, int r, int cl, int cr, int idx) { if(cl>r || cr> n; vector> v1,v2; for(int i=0;i> a >> b; v1.pb({a,b}); } for(int i=0;i> a >> b; v2.pb({a,b}); } sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); int freq[400008]; memset(segtree, 0, sizeof(segtree)); memset(freq, 0, sizeof(freq)); vectortempv; for(auto var:v1) tempv.pb(var[1]); for(auto var:v2) tempv.pb(var[1]); sort(tempv.begin(), tempv.end()); int i=0,j=0,count=1; mapmp; while(i
ADD COMMENTlink 15 months ago sumeet kumar sahoo • 290

Login before adding your answer.

Similar Posts
Loading Similar Posts