Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <math.h>
- #include <sstream>
- #include <string>
- #include <iostream>
- #include <limits>
- #include <stdexcept>
- #include <unordered_set>
- #include <unordered_map>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cstdlib>
- #include <numeric>
- #include <array>
- #include <iomanip> // std::setprecision
- #include <tuple>
- #include <iostream>
- #include <fstream>
- using namespace std;
- #define int int64_t
- int32_t main_DA(){ //== Destorying Array //== еЌЉзќЎеЌЉй†’дёе±…з„¶ AC дє†
- /*
- https://codeforces.com/problemset/problem/722/C
- data structures
- dsu
- *1600
- */
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- vector<int> given(n, -1);
- for( int i = 0; i < n; ++i) {
- cin >> given[i];
- }
- vector<int> rm_order(n, -1);
- for( int i = 0; i < n; ++i) {
- cin >> rm_order[i];
- }
- vector<int> semiPref(n+1, 0);
- semiPref[0] = 0;
- for( int j = 0; j < n; ++j) {
- semiPref[j+1] = semiPref[j] + given[j];
- }
- /*
- since the biggest segment sum can only decrease, when array is being destoried
- we only need to update the largest segment sum on each element removal
- */
- set< pair<int,int> > segments; //== all current segSums' range [L, R) , sorted by LeftSide boarders
- multiset< pair<int, int>> sums_LeftEnd; //== will keep update the < segSum : its_Left_boarder > пјџпјџ
- int sumMax = semiPref[n] - semiPref[0];
- sums_LeftEnd.insert({sumMax, 0});
- segments.insert({0, n});
- //cout << "bp, check inputs" << endl;
- for( int i = 0; i < n; ++i) {
- int rm = rm_order[i] - 1; //== 0_based index
- auto& segToSplit = *(--segments.lower_bound({ rm+1, -1 })); //== check corner case when only 1 segment exists
- int leftPos = segToSplit.first;
- int rightPos = segToSplit.second;
- segments.erase({leftPos, rightPos});
- segments.insert({leftPos, rm}); //== right side ends BEFORE rm
- segments.insert({rm+1, rightPos});
- //== all below is semi_open_intervals //== some of below are redundant !!!
- int oldSum = semiPref[rightPos] - semiPref[leftPos];
- auto& sum_L_ToSplit = *(sums_LeftEnd.find({oldSum,leftPos})); //== Is multiSet needed, or regular Set is enough ???
- sums_LeftEnd.erase(sum_L_ToSplit);
- int leftNewSum = semiPref[rm] - semiPref[leftPos];
- sums_LeftEnd.insert({leftNewSum, leftPos});
- int rightNewSum = semiPref[rightPos] - semiPref[rm + 1];
- sums_LeftEnd.insert({rightNewSum,rm + 1});
- cout << (--sums_LeftEnd.end())->first <<endl;
- }
- return 0;
- }
- int32_t main(){ //== Pair of Topics // QJ self try 2 pointers
- /*
- https://codeforces.com/group/Ap6SQK7app/contest/309423/problem/F
- https://codeforces.com/problemset/problem/1324/D
- binary search
- data structures
- sortings
- two pointers
- *1400
- */
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- int n;
- cin >> n;
- vector<int> teachers(n,-1);
- vector<int> students(n,-1);
- // vector< pair<int, int>> diff_pairs(n, {-1, -1}); // do I need this ?
- vector<int> diff_val(n); //== can we use Set instead ?????, so we can use set's lower_bound directly
- for( int i = 0; i < n; ++i) {
- cin >> teachers[i];
- }
- for( int i = 0; i < n; ++i) {
- cin >> students[i];
- // diff_pairs[i] = { teachers[i], students[i]};
- diff_val[i] = teachers[i] - students[i];
- }
- sort(diff_val.begin(), diff_val.end());
- int answer = 0;
- for( int i = 0; i < n; ++i) {
- int first_good = lower_bound( diff_val.begin(), diff_val.end(), -diff_val[i] + 1 ) - diff_val.begin();
- first_good = max(first_good, i + 1);
- int goodPairsCnt = n - first_good; //== bug here, but don't know how to fix :(
- answer += goodPairsCnt;
- }
- // cout << "bp check inputs" << endl;
- cout << answer ; //== WA ????
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment