test/util/Zarts.test.cpp

• View this file on GitHub
• Last update: 2023-05-30 04:54:08+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_4_A

Depends on

• Zarts - 座標圧縮 (lib/00-util/Zarts.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_4_A"

#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <map>
using namespace std;
#include "../../lib/00-util/Zarts.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<long long> x(N*2),y(N*2);
    for(int i=0;i<N;++i) {
        cin >> x[i*2+0];
        cin >> y[i*2+0];
        cin >> x[i*2+1];
        cin >> y[i*2+1];
    }
    Zarts<long long> Zx(x),Zy(y);
    vector<vector<long long>> grid(Zy.size(),vector<long long>(Zx.size(),0));
    for(int i=0;i<N;++i) {
        long long x1=Zx.compressed[i*2+0],y1=Zy.compressed[i*2+0],x2=Zx.compressed[i*2+1],y2=Zy.compressed[i*2+1];
        grid[y1][x1]++;
        grid[y1][x2]--;
        grid[y2][x1]--;
        grid[y2][x2]++;
    }    
    for(int i=0;i<Zy.size();++i) {
        for(int j=1;j<Zx.size();++j) {
            grid[i][j] += grid[i][j-1];
        }
    }
    for(int j=0;j<Zx.size();++j) {
        for(int i=1;i<Zy.size();++i) {
            grid[i][j] += grid[i-1][j];
        }
    }
    long long ans = 0;
    for(int i=0;i+1<Zy.size();++i) {
        for(int j=0;j+1<Zx.size();++j) {
            if(grid[i][j]) ans += (Zy.get_value(i+1)-Zy.get_value(i))*(Zx.get_value(j+1)-Zx.get_value(j));
        }
    }
    cout << ans << endl;
	return 0;
}

#line 1 "test/util/Zarts.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_4_A"

#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <map>
using namespace std;
#line 1 "lib/00-util/Zarts.cpp"
/*
 * @title Zarts - 座標圧縮
 * @docs md/util/Zarts.md
 */
template<class T> class Zarts{
    vector<T> value;
    map<T,int> key;
    size_t sz;
public:
    vector<int> compressed;
    Zarts(const vector<T> & ar, int light_flag = 0, T pre=-1) : compressed(ar.size()) {
        if(!light_flag) {
            for (auto &e : ar) key[e];
            int cnt=0;
            for (auto &e : key) e.second = cnt++;
            for (int i=0;i<ar.size();++i) compressed[i]=key[ar[i]];
            value.resize(key.size());
            for (auto &e : key) value[e.second] = e.first;
            sz = cnt;
        }
        else {
            vector<pair<int,int>> ord(ar.size());
            for(int i=0;i<ar.size();++i) ord[i]={ar[i],i};
            sort(ord.begin(),ord.end());
            int cnt=-1;
            for(int i=0;i<ar.size();++i) {
                if(pre < ord[i].first) cnt++;
                compressed[ord[i].second] = cnt;
                pre = ord[i].first;
            }
            sz = cnt+1;
        }
    }
    T get_value(int key) {
        return value[key];
    }
    int get_key(T value) {
        assert(key.count(value));
        return key[value];
    }
    size_t size() {
        return sz;
    }
};
#line 10 "test/util/Zarts.test.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<long long> x(N*2),y(N*2);
    for(int i=0;i<N;++i) {
        cin >> x[i*2+0];
        cin >> y[i*2+0];
        cin >> x[i*2+1];
        cin >> y[i*2+1];
    }
    Zarts<long long> Zx(x),Zy(y);
    vector<vector<long long>> grid(Zy.size(),vector<long long>(Zx.size(),0));
    for(int i=0;i<N;++i) {
        long long x1=Zx.compressed[i*2+0],y1=Zy.compressed[i*2+0],x2=Zx.compressed[i*2+1],y2=Zy.compressed[i*2+1];
        grid[y1][x1]++;
        grid[y1][x2]--;
        grid[y2][x1]--;
        grid[y2][x2]++;
    }    
    for(int i=0;i<Zy.size();++i) {
        for(int j=1;j<Zx.size();++j) {
            grid[i][j] += grid[i][j-1];
        }
    }
    for(int j=0;j<Zx.size();++j) {
        for(int i=1;i<Zy.size();++i) {
            grid[i][j] += grid[i-1][j];
        }
    }
    long long ans = 0;
    for(int i=0;i+1<Zy.size();++i) {
        for(int j=0;j+1<Zx.size();++j) {
            if(grid[i][j]) ans += (Zy.get_value(i+1)-Zy.get_value(i))*(Zx.get_value(j+1)-Zx.get_value(j));
        }
    }
    cout << ans << endl;
	return 0;
}

Back to top page