rembocoder

Untitled

Apr 24th, 2023
686
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 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. void addCut(multiset<pair<int, int>>& segs, multiset<int>& lengths, int u) {
  30.     auto it = --segs.lower_bound({u+1, -1});
  31.  
  32.     int currX = it->first;
  33.     int currY = it->second;
  34.  
  35.     segs.erase(it);
  36.     segs.insert({currX, u});
  37.     segs.insert({u, currY});
  38.  
  39.     lengths.erase(lengths.find(currY - currX));
  40.     lengths.insert(u-currX);
  41.     lengths.insert(currY-u);
  42. }
  43.  
  44. int32_t main(){ //==
  45.     /*
  46.      https://codeforces.com/group/Ap6SQK7app/contest/309423/problem/C
  47.  
  48.      "AM-CP-2023-04-19=Set_lower_bound_vessel_+_Glass_Carv"
  49.      */
  50.  
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(0); cout.tie(0);
  53.  
  54.     int w, h, N;
  55.     cin >> w >> h >> N;
  56.     multiset<pair<int, int>> segRow, segColumn; // segment[x, y] positions, to remove 1 older segment, insert 2 new segments
  57.     multiset<int> rowLength, columnLength;
  58.  
  59.     segRow.insert({0, h});
  60.     segColumn.insert({0, w});
  61.     rowLength.insert(h);
  62.     columnLength.insert(w);
  63.  
  64.     while( N-- ){
  65.         char Dir;
  66.         int u; //location
  67.         cin >> Dir >> u;
  68.         if( Dir == 'H'){ // update rowLength, and insert new seg into "segRow" at the location
  69.             addCut(segRow, rowLength, u);
  70.         } else {
  71.             addCut(segColumn, columnLength, u);
  72.         }
  73.         cout << (*--rowLength.end()) * (*--columnLength.end()) << endl;
  74.     }
  75.  
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment