Advertisement
Josif_tepe

Untitled

Sep 28th, 2023
851
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <set>
  7. #include <cstring>
  8. #include <stack>
  9. #include <algorithm>
  10. //#include <bits/stdc++.h>
  11. using namespace std;
  12. typedef long long ll;
  13. const int maxn = 3e5 + 10;
  14. const ll INF = 3e16 + 10;
  15.  
  16. struct node {
  17.     int y, x1, x2;
  18.     bool up;
  19.     node () {}
  20.     node(int _y, int _x1, int _x2, bool _up) {
  21.         y = _y;
  22.         x1 = _x1;
  23.         x2 = _x2;
  24.         up = _up;
  25.     }
  26.     bool operator < (const node &tmp) const {
  27.         return y < tmp.y;
  28.     }
  29. };
  30. int main() {
  31.     ios_base::sync_with_stdio(false);
  32.     int L, W;
  33.     cin >> L >> W;
  34.     int months;
  35.     cin >> months;
  36.     int n;
  37.     cin >> n;
  38.     vector<pair<int, int>> buildings(n);
  39.     vector<node> v;
  40.     for(int i = 0; i < n; i++) {
  41.         cin >> buildings[i].first >> buildings[i].second;
  42.        
  43.         v.push_back(node(max(1, buildings[i].second - months), max(1, buildings[i].first - months), min(L, buildings[i].first + months), true));
  44.         v.push_back(node(min(W, buildings[i].second + months), max(1, buildings[i].first - months), min(L, buildings[i].first + months), false));
  45.     }
  46.     sort(v.begin(), v.end());
  47.     stack<int> st;
  48.     ll result = 0;
  49.     for(int x = 1; x <= L; x++) {
  50.         int st_max = 0;
  51.  
  52.         for(int i = 0; i < (int) v.size(); i++) {
  53.             if(v[i].x1 <=  x and x <= v[i].x2) {
  54.                 if(v[i].up) {
  55.                     st.push(v[i].y);
  56.                 }
  57.                 else {
  58.                     if(st.size() == 1) {
  59.                         result += v[i].y - max(st.top(), st_max) + 1;
  60.                         st_max = v[i].y + 1;
  61.                     }
  62.                     st.pop();
  63.                 }
  64.             }
  65.         }
  66.        
  67.     }
  68.     cout << result << endl;
  69.     return 0;
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement