読者です 読者をやめる 読者になる 読者になる

AOJ 0509 Sheets

問題概要

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

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

解法

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

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

どこに +1 して -1 するかは,y座標をindexとする vectorvector を持っておけば良い.

これでなんとか解ける.
計算量は 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;
        }
    }
}