POINTWISESUM - Editorial

editorial
1

PROBLEM LINK:

Practice

Author: Kunal Demla
Editorialist: Kunal Demla

DIFFICULTY:

Medium - hard

PREREQUISITES:

priority queues or prefix sum

SOLUTIONS:

Setters' Solution 
 #include<bits/stdc++.h>
 using namespace std;
 #define ll long long int
 typedef pair<int,pair<int,int>> pp;
 
 void solve()
 {
     ll n,m,x,y,i,j,k,q;
     cin>>n;
     vector<vector<pair<int,int>>> v(n);
     for(i=0;i<n;i++){
         cin>>x;
         v[i].resize(x);
     }
     for(i=0;i<n;i++)
         for(j=0;j<v[i].size();j++)
             cin>>v[i][j].first>>v[i][j].second;
     priority_queue<pp, vector<pp>, greater<pp>> pq;
     for(i=0;i<n;i++){
         for(auto v1:v[i]){
             pq.push({v1.first,{v1.second,i}});
         }
     }
     vector<int> temp(n,0);
     vector<pair<int,int>> ans;
     int t2=0;
     while(!pq.empty()){
         int t1=pq.top().first;
         // vector<int> used(n,0);
         while(!pq.empty()&&pq.top().first==t1){
             t2+=pq.top().second.first - temp[pq.top().second.second];
             temp[pq.top().second.second] = pq.top().second.first;
             // used[pq.top().second.second]++;
             pq.pop();
         }
         ans.push_back({t1,t2});
     }
     for(i=0;i<ans.size();i++){
         if((i&&ans[i-1].second!=ans[i].second)||!i)
         cout<<ans[i].first<<" "<<ans[i].second<<endl;
     }
 }
 
 int main()
 {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 cout.tie(NULL);
 
 #ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("error.txt", "w", stderr);
 freopen("output.txt", "w", stdout);
 #endif
 
 int t=1;
 // cout<<t<<endl;
 // ${2:is Single Test case?}cin>>t;
 cin>>t;
 int n=t;
 while(t--)
 {
     //cout<<"Case #"<<n-t<<": ";
     solve();
     cout<<"\n";
 }
 
 cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
 return 0;
 }