Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <queue>
- #include <iostream>
- #include <vector>
- #include <cstring>
- #include <iostream>
- #include <set>
- #include <cstring>
- #include <stack>
- #include <algorithm>
- //#include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 3e5 + 10;
- const ll INF = 3e16 + 10;
- struct node {
- int y, x1, x2;
- bool up;
- node () {}
- node(int _y, int _x1, int _x2, bool _up) {
- y = _y;
- x1 = _x1;
- x2 = _x2;
- up = _up;
- }
- bool operator < (const node &tmp) const {
- return y < tmp.y;
- }
- };
- int main() {
- ios_base::sync_with_stdio(false);
- int L, W;
- cin >> L >> W;
- int months;
- cin >> months;
- int n;
- cin >> n;
- vector<pair<int, int>> buildings(n);
- vector<node> v;
- for(int i = 0; i < n; i++) {
- cin >> buildings[i].first >> buildings[i].second;
- v.push_back(node(max(1, buildings[i].second - months), max(1, buildings[i].first - months), min(L, buildings[i].first + months), true));
- v.push_back(node(min(W, buildings[i].second + months), max(1, buildings[i].first - months), min(L, buildings[i].first + months), false));
- }
- sort(v.begin(), v.end());
- stack<int> st;
- ll result = 0;
- for(int x = 1; x <= L; x++) {
- int st_max = 0;
- for(int i = 0; i < (int) v.size(); i++) {
- if(v[i].x1 <= x and x <= v[i].x2) {
- if(v[i].up) {
- st.push(v[i].y);
- }
- else {
- if(st.size() == 1) {
- result += v[i].y - max(st.top(), st_max) + 1;
- st_max = v[i].y + 1;
- }
- st.pop();
- }
- }
- }
- }
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement