Submission #873995

#	Time	Username	Problem	Language	Result	Execution time	Memory
873995		azberjibiou	절취선 (JOI14_ho_t5)	C++17	20 / 100	116 ms	25012 KiB

2014_ho_t5

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<pair<int, int>, pair<int, int>>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=210005;
const int mxM=500004;
const int mxK=30;
const int MOD=1'000'000'007;
const ll INF=8e18;
typedef struct BIT{
    int fen[mxN], n;
    void set_n(int m){n=m;}
    void upd(int idx, int val){for(;idx<=n;idx+=(idx&(-idx))) fen[idx]+=val;}
    int sum(int idx){int res=0; for(;idx>0;idx-=(idx&(-idx))) res+=fen[idx]; return res;}
    int solv(int s, int e){return sum(e)-sum(s-1);}
}BIT;
typedef struct line{
    ll x1, x2, y, xy;   ///xy=1: x축과 평행 2: y축과 평행
    line() : x1(), x2(), y(), xy() {}
    line(ll x1, ll x2, ll y, ll xy) : x1(x1), x2(x2), y(y), xy(xy) {}
}line;
int N;
ll H, W;
vector <line> v;
vector <line> ev;
BIT T1;
ll cntV, cntE;
void input(){
    cin >> W >> H >> N;
    v.emplace_back(0, W, 0, 1);
    v.emplace_back(0, W, H, 1);
    v.emplace_back(0, H, 0, 2);
    v.emplace_back(0, H, W, 2);
    for(int i=1;i<=N;i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a==c)    v.emplace_back(b, d, c, 2);
        else    v.emplace_back(a, c, b, 1);
    }
}
void coor_comp(){
    vector <ll> crx, cry;
    for(auto &[x1, x2, y, xy] : v){
        x1=3*x1-1, x2=3*x2+1, y=3*y;
        if(xy==1)   crx.push_back(x1), crx.push_back(x2), cry.push_back(y);
        else    cry.push_back(x1), cry.push_back(x2), crx.push_back(y);
    }
    sort(all(crx));
    crx.erase(unique(all(crx)), crx.end());
    sort(all(cry));
    cry.erase(unique(all(cry)), cry.end());
    for(auto &[x1, x2, y, xy] : v){
        if(xy==1){
            x1=lower_bound(all(crx), x1)-crx.begin()+1;
            x2=lower_bound(all(crx), x2)-crx.begin()+1;
            y=lower_bound(all(cry), y)-cry.begin()+1;
        }
        else{
            x1=lower_bound(all(cry), x1)-cry.begin()+1;
            x2=lower_bound(all(cry), x2)-cry.begin()+1;
            y=lower_bound(all(crx), y)-crx.begin()+1;
        }
        if(xy==1) ev.emplace_back(x1, x2, y, xy);
        else ev.emplace_back(y, 1, x1, xy), ev.emplace_back(y, -1, x2, xy);
    }
    W=crx.size(), H=cry.size();
    sort(all(ev), [](line a, line b){return a.y<b.y;});
}
void count_VE(){
    T1.set_n(W);
    cntV=2*(N+4);
    for(auto [x1, x2, y, xy] : ev){
        if(xy==1) cntV+=T1.solv(x1, x2);
        else T1.upd(x1, x2);
        //printf("x1=%d, x2=%d, y=%d, xy=%d\n", x1, x2, y, xy);
    }
    //2*(N+4)+4*(cntV-2*(N+4))=2*cntE
    cntE=2*cntV-3*(N+4);
}
int main()
{
    gibon
    input();
    coor_comp();
    count_VE();
    //V-E+F=2
    //printf("cntE=%lld, cntV=%lld\n", cntE, cntV);
    cout << cntE-cntV+1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 50