rembocoder

Untitled

May 1st, 2023
893
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.13 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <sstream>
  4. #include <string>
  5. #include <iostream>
  6. #include <limits>
  7. #include <stdexcept>
  8. #include <unordered_set>
  9. #include <unordered_map>
  10. #include <vector>
  11. #include <string>
  12. #include <map>
  13. #include <set>
  14. #include <stack>
  15. #include <queue>
  16. #include <algorithm>
  17. #include <cstdlib>
  18. #include <numeric>
  19. #include <array>
  20. #include <iomanip>      // std::setprecision
  21. #include <tuple>
  22. #include <iostream>
  23. #include <fstream>
  24.  
  25. using namespace std;
  26.  
  27. #define int int64_t
  28.  
  29. int32_t main_DA(){ //== Destorying Array //== еЌЉзќЎеЌЉй†’дё­е±…з„¶ AC дє†
  30.     /*
  31.      https://codeforces.com/problemset/problem/722/C
  32.      data structures
  33.      dsu
  34.      *1600
  35.      */
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0); cout.tie(0);
  38.  
  39.     int n;
  40.     cin >> n;
  41.     vector<int> given(n, -1);
  42.     for( int i = 0; i < n; ++i) {
  43.         cin >> given[i];
  44.     }
  45.     vector<int> rm_order(n, -1);
  46.     for( int i = 0; i < n; ++i) {
  47.         cin >> rm_order[i];
  48.     }
  49.  
  50.     vector<int> semiPref(n+1, 0);
  51.     semiPref[0] = 0;
  52.     for( int j = 0; j < n; ++j) {
  53.         semiPref[j+1] = semiPref[j] + given[j];
  54.     }
  55.  
  56.     /*
  57.      since the biggest segment sum can only decrease, when array is being destoried
  58.      we only need to update the largest segment sum on each element removal
  59.      */
  60.     set< pair<int,int> > segments; //== all current segSums' range [L, R) , sorted by LeftSide boarders
  61.     multiset< pair<int, int>> sums_LeftEnd; //== will keep update the < segSum : its_Left_boarder > пјџпјџ
  62.     int sumMax = semiPref[n] - semiPref[0];
  63.     sums_LeftEnd.insert({sumMax, 0});
  64.  
  65.     segments.insert({0, n});
  66.     //cout << "bp, check inputs" << endl;
  67.  
  68.     for( int i = 0; i < n; ++i) {
  69.         int rm = rm_order[i] - 1; //== 0_based index
  70.  
  71.         auto& segToSplit = *(--segments.lower_bound({ rm+1, -1 })); //== check corner case when only 1 segment exists
  72.         int leftPos = segToSplit.first;
  73.         int rightPos = segToSplit.second;
  74.         segments.erase({leftPos, rightPos});
  75.         segments.insert({leftPos, rm}); //== right side ends BEFORE rm
  76.         segments.insert({rm+1, rightPos});
  77.  
  78.  
  79.         //== all below is semi_open_intervals //== some of below are redundant !!!
  80.         int oldSum = semiPref[rightPos] - semiPref[leftPos];
  81.         auto& sum_L_ToSplit = *(sums_LeftEnd.find({oldSum,leftPos})); //== Is multiSet needed, or regular Set is enough ???
  82.         sums_LeftEnd.erase(sum_L_ToSplit);
  83.  
  84.         int leftNewSum = semiPref[rm] - semiPref[leftPos];
  85.         sums_LeftEnd.insert({leftNewSum, leftPos});
  86.  
  87.         int rightNewSum = semiPref[rightPos] - semiPref[rm + 1];
  88.         sums_LeftEnd.insert({rightNewSum,rm + 1});
  89.  
  90.         cout << (--sums_LeftEnd.end())->first <<endl;
  91.     }
  92.  
  93.     return 0;
  94. }
  95.  
  96. int32_t main(){ //== Pair of Topics // QJ self try 2 pointers
  97.     /*
  98.      https://codeforces.com/group/Ap6SQK7app/contest/309423/problem/F
  99.      https://codeforces.com/problemset/problem/1324/D
  100.      binary search
  101.      data structures
  102.      sortings
  103.      two pointers
  104.      *1400
  105.      */
  106.     ios_base::sync_with_stdio(false);
  107.     cin.tie(0); cout.tie(0);
  108.     int n;
  109.     cin >> n;
  110.     vector<int> teachers(n,-1);
  111.     vector<int> students(n,-1);
  112. //    vector< pair<int, int>> diff_pairs(n, {-1, -1}); // do I need this ?
  113.     vector<int> diff_val(n); //== can we use Set instead ?????, so we can use set's lower_bound directly
  114.     for( int i = 0; i < n; ++i) {
  115.         cin >> teachers[i];
  116.     }
  117.     for( int i = 0; i < n; ++i) {
  118.         cin >> students[i];
  119. //        diff_pairs[i] = { teachers[i], students[i]};
  120.         diff_val[i] = teachers[i] - students[i];
  121.     }
  122.     sort(diff_val.begin(), diff_val.end());
  123.     int answer = 0;
  124.     for( int i = 0; i < n; ++i) {
  125.         int first_good = lower_bound( diff_val.begin(), diff_val.end(), -diff_val[i] + 1 ) - diff_val.begin();
  126.         first_good = max(first_good, i + 1);
  127.         int goodPairsCnt = n - first_good; //== bug here, but don't know how to fix :(
  128.         answer += goodPairsCnt;
  129.     }
  130.  
  131. //    cout << "bp check inputs" << endl;
  132.     cout << answer ; //== WA ????
  133.     return 0;
  134. }
  135.  
Advertisement
Add Comment
Please, Sign In to add comment