Advertisement
mickypinata

AJMEW-T002: Group Rectangle

Sep 3rd, 2021
1,155
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef pair<int, int> pii;
  6.  
  7. struct linear {
  8.     lli m, c;
  9.     linear(): m(0), c(0) {};
  10.     linear(lli m, lli c): m(m), c(c) {};
  11. };
  12.  
  13. typedef pair<linear, lli> pLl;
  14.  
  15. const int N = 5e4;
  16.  
  17. lli dp[N + 1];
  18. vector<pii> recs, newRecs(1, pii(0, 1e9));
  19. deque<pLl> cht;
  20.  
  21. lli intersect(linear &a, linear &b){
  22.     lli x = b.c - a.c;
  23.     lli y = a.m - b.m;
  24.     return x / y + !((x < 0) != (y < 0) || (x % y == 0));
  25. }
  26.  
  27. void chtInsert(linear l){
  28.     if(!cht.empty() && cht.back().first.m == l.m){
  29.         if(cht.back().first.c > l.c){
  30.             cht.pop_back();
  31.             chtInsert(l);
  32.         }
  33.         return;
  34.     }
  35.     while(!cht.empty() && cht.back().second >= intersect(cht.back().first, l)){
  36.         cht.pop_back();
  37.     }
  38.     if(cht.empty()){
  39.         cht.emplace_back(l, 0);
  40.     } else {
  41.         cht.emplace_back(l, intersect(cht.back().first, l));
  42.     }
  43. }
  44.  
  45. lli chtQuery(lli x){
  46.     while(cht.size() > 1 && next(cht.begin()) -> second <= x){
  47.         cht.pop_front();
  48.     }
  49.     linear ans = cht.front().first;
  50.     return ans.m * x + ans.c;
  51. }
  52.  
  53. int main(){
  54.  
  55.     int n;
  56.     scanf("%d", &n);
  57.     for(int i = 1; i <= n; ++i){
  58.         int x, y;
  59.         scanf("%d%d", &x, &y);
  60.         recs.emplace_back(x, y);
  61.     }
  62.     sort(recs.begin(), recs.end());
  63.     for(pii p : recs){
  64.         while(!newRecs.empty() && newRecs.back().first <= p.first && newRecs.back().second <= p.second){
  65.             newRecs.pop_back();
  66.         }
  67.         newRecs.push_back(p);
  68.     }
  69.     dp[0] = 0;
  70.     for(int i = 1; i <= newRecs.size(); ++i){
  71.         chtInsert(linear(newRecs[i - 1].second, dp[i - 1]));
  72.         dp[i] = chtQuery(newRecs[i - 1].first);
  73.     }
  74.     cout << dp[newRecs.size()];
  75.  
  76.     return 0;
  77. }
  78.  
Advertisement
RAW Paste Data Copied
Advertisement