제출 #1178204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178204		vicvic	Dominance (CEOI08_dominance)	C++20	100 / 100	27 ms	612 KiB

dominance

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>
#define int long long
using namespace std;
struct event
{
    int x, ys, ye, value;
};
int w, h, n, w_cells, b_cells;
void solve (vector <event> vec)
{
    sort (vec.begin(), vec.end(), [] (event a, event b) {return a.x<b.x;});
    vector <int> ys;
    for (auto chestie : vec)
    {
        ys.push_back ({chestie.ys});
        ys.push_back ({chestie.ye+1});
    }
    sort (ys.begin(), ys.end());
    ys.resize (unique (ys.begin(), ys.end())-ys.begin());
    int k=ys.size();
    vector <int> mars (k+1, 0);
    auto gety = [&] (int val)
    {
        return lower_bound (ys.begin(), ys.end(), val)-ys.begin()+1;
    };
    for (int i=0;i+1<vec.size();i++)
    {
        for (int j=gety (vec[i].ys);j<gety (vec[i].ye+1);j++)
            mars[j]+=vec[i].value;
        for (int j=1;j<k;j++)
        {
            int ret=(vec[i+1].x-vec[i].x)*(ys[j]-ys[j-1]);
            if (mars[j]<0) b_cells+=ret;
            if (mars[j]>0) w_cells+=ret;
        }
    }
}
void addTo (vector <event> &vec, int x, int y, int r, int v)
{
    vec.push_back ({(x+y-r) >> 1, (-x+y-r) >> 1, (-x+y+r) >> 1, v});
    vec.push_back ({((x+y+r) >> 1) +1, (-x+y-r) >> 1, (-x+y+r) >> 1, -v});
}
int32_t main ()
{
    vector <event> even, odd;
    cin >> w >> h >> n;
    for (int i=1;i<=n;i++)
    {
        char type;
        int x, y, r;
        cin >> type >> x >> y >> r;
        int value=(type=='W'?1:-1);
        int displacement=(x+y+r)%2;
        addTo (even, x, y, r-displacement, value);
        addTo (odd, x, y, r+displacement-1, value);
    }
    solve (even);
    solve (odd);
    cout << w_cells << " " << b_cells << "\n";
    return 0;
}

• Subtask 1: 100 / 100