boj2601.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
 
using namespace std;
 
#define MAXN 101000
 
int IndexTree1[2 * 4 * MAXN];
int IndexTree2[2 * 4 * MAXN];
int p = 1;
 
typedef struct Rectangle{
    int x1, y1, x2, y2;
};
 
typedef pair<int, pair<int, int> > Event;
 
bool compare(const Event& i, const Event& j){
    if (i.first == j.first)
        return i.second.first > j.second.first;
    return i.first < j.first;
}
 
void update(int left, int right, int value){
    left += p;
    right += p;
    while (left <= right){
        if (left & 1){
            IndexTree1[left] += value;
            IndexTree2[left] += value;
            for (int i = (left >> 1); i >= 1; i >>= 1)
                IndexTree2[i] = max(IndexTree2[i * 2], IndexTree2[i * 2 + 1]) + IndexTree1[i];
            left++;
 
        }
        if (!(right & 1)){
            IndexTree1[right] += value;
            IndexTree2[right] += value;
            for (int i = (right >> 1); i >= 1; i >>= 1)
                IndexTree2[i] = max(IndexTree2[i * 2], IndexTree2[i * 2 + 1]) + IndexTree1[i];
            right--;
        }
        left >>= 1; right >>= 1;
    }
}
 
int CountArea(const vector<Rectangle>& rec){
    if (rec.empty()) return 0;
 
    //x, y좌표 각각 다른 배열로 옮기기
    vector<int> ys;
    vector<Event> xs;
    for (int i = 0; i < rec.size(); i++){
        ys.push_back(rec[i].y1);
        ys.push_back(rec[i].y2);
        xs.push_back(Event(rec[i].x1, make_pair(1, i)));
        xs.push_back(Event(rec[i].x2, make_pair(-1, i)));
    }
    //정렬
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(xs.begin(), xs.end(), compare);
 
    //y맵 구성
    map<int, int> yindex;
    for (int i = 0; i< ys.size(); i++)
        yindex[ys[i]] = i;
 
    //인덱스 트리 p셋팅
    int temp = ys.size() + 1000;
    while (temp > p) p <<= 1;
 
    int ret = 0;
    for (int i = 0; i < xs.size(); i++){
        int recNum = xs[i].second.second, delta = xs[i].second.first;
        int nowx = xs[i].first;
        int nowy1 = rec[recNum].y1, nowy2 = rec[recNum].y2;
 
        //y스위치 업데이트
        update(yindex[nowy2], yindex[nowy1], delta);
 
        ret = max(ret, IndexTree2[1]);
    }
    return ret;
}
 
int main(){
    Rectangle bound;
    cin >> bound.x1 >> bound.y1 >> bound.x2 >> bound.y2;
    int W, N;
    cin >> W;
    cin >> N;
    vector<Rectangle> input_temp(N + 10);
    vector<Rectangle> input;
 
    for (int i = 0; i < N; i++){
        scanf("%d%d%d%d", &input_temp[i].x1, &input_temp[i].y1, &input_temp[i].x2, &input_temp[i].y2);
        if ((input_temp[i].x2 - input_temp[i].x1 > W) || (input_temp[i].y1 - input_temp[i].y2 > W)) 
            continue;
        Rectangle tt;
        tt.x2 = min(input_temp[i].x1 + W, bound.x2);
        tt.x1 = input_temp[i].x2;
        tt.y1 = min(input_temp[i].y2 + W, bound.y1);
        tt.y2 = input_temp[i].y1;       
        input.push_back(tt);
    }
    cout << CountArea(input) << endl;
    return 0;
}