AOJ 0509 Sheets

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509

問題概要

平面座標に n 個の長方形がある．重なっていることもある．
それらがつくる図形の面積と，周の長さを求めよ．

・制約
1 <= n <= 10000
長方形の左下，右上の座標の x, y 座標は，共に 0 以上 10000 以下である．

解法

累積和（いもす法）でやる．
ただし愚直に2次元累積和を取ると MLE する．
そのため，まず0行目から横一行（縦一列でもよい）ずつ見ていくようにして，次の行を見るときは前の行の値を使うようにする．
こうすると，それ以前の値を保存する必要が無いので，MLEを防げる．
流れとしては，

• 横で累積和をとる．
• そのあと，前の行の累積和を足す．
• 累積和の値が1以上であれば面積に1追加，図形の端（自身と四方の累積和を比較すればわかる）であれば周の長さに1追加する．

どこに +1 して -1 するかは，y座標をindexとする vector の vector を持っておけば良い．

これでなんとか解ける．
計算量は O(XY) = 10^8 で，定数倍かかるのでかなりギリギリになった．

賢く書けばもうちょい早くなるかも．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using P = pair<int, int>;

constexpr int MAX_Y = 10003;
constexpr int MAX_X = 10003;

int main() {
    int n, r;
    while(cin >> n >> r, n) {
        vector<vector<P>> v(MAX_Y);
        for(int i=0; i<n; ++i) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            v[y1+1].emplace_back(x1+1, 1);
            v[y1+1].emplace_back(x2+1, -1);
            v[y2+1].emplace_back(x1+1, -1);
            v[y2+1].emplace_back(x2+1, 1);
        }
        vector<vector<int>> sum(2, vector<int>(MAX_X));
        int S = 0, len = 0;
        for(int i=0; i<MAX_Y; ++i) {
            int now = i % 2, pre = (i+1) % 2;
            fill(sum[now].begin(), sum[now].end(), 0);
            for(int j=0; j<v[i].size(); ++j) {
                sum[now][v[i][j].first] += v[i][j].second;
            }
            for(int j=0; j<MAX_X; ++j) {
                sum[now][j+1] += sum[now][j];
                sum[now][j] += sum[pre][j];
            }
            for(int j=0; j<MAX_X; ++j) {
                S += sum[now][j] > 0;
                len += ((sum[pre][j] > 0) != (sum[now][j] > 0));
                len += ((sum[now][j] > 0) != (sum[now][j+1] > 0));
            }
        }
        
        if(r == 1) {
            cout << S << endl;
        } else {
            cout << S << '\n' << len << endl;
        }
    }
}