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
- void addCut(multiset<pair<int, int>>& segs, multiset<int>& lengths, int u) {
- auto it = --segs.lower_bound({u+1, -1});
- int currX = it->first;
- int currY = it->second;
- segs.erase(it);
- segs.insert({currX, u});
- segs.insert({u, currY});
- lengths.erase(lengths.find(currY - currX));
- lengths.insert(u-currX);
- lengths.insert(currY-u);
- }
- int32_t main(){ //==
- /*
- https://codeforces.com/group/Ap6SQK7app/contest/309423/problem/C
- "AM-CP-2023-04-19=Set_lower_bound_vessel_+_Glass_Carv"
- */
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- int w, h, N;
- cin >> w >> h >> N;
- multiset<pair<int, int>> segRow, segColumn; // segment[x, y] positions, to remove 1 older segment, insert 2 new segments
- multiset<int> rowLength, columnLength;
- segRow.insert({0, h});
- segColumn.insert({0, w});
- rowLength.insert(h);
- columnLength.insert(w);
- while( N-- ){
- char Dir;
- int u; //location
- cin >> Dir >> u;
- if( Dir == 'H'){ // update rowLength, and insert new seg into "segRow" at the location
- addCut(segRow, rowLength, u);
- } else {
- addCut(segColumn, columnLength, u);
- }
- cout << (*--rowLength.end()) * (*--columnLength.end()) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment