Submission #35175

#	Time	Username	Problem	Language	Result	Execution time	Memory
35175		bql20000	도로 건설 사업 (JOI13_construction)	C++14	0 / 100	5000 ms	137660 KiB

construction

#include <bits/stdc++.h>

#define ff(i,a,b)       for(int i=(a), _b=(b); i<=_b; ++i)
#define gg(i,a,b)       for(int i=(a), _b=(b); i>=_b; --i)
#define REP(i,b)        for(int i=(0), _b=(b); i< _b; ++i)
#define endl            '\n'
#define long            long long
#define ALL(x)          (x).begin(), (x).end()
#define Love(a)         {cerr << #a << " = " << a << endl;}
#define _               << "," <<
#define BIT(i, x)       (((x)>>(i))&1)
#define X               first
#define Y               second

#define NAME            "Construction"

using namespace std;
const int N = 2e5 +  8, maxQ = 5e5 + 7;
typedef pair<int, int> ii;

struct HCN {
    int x, y, u, v;
    HCN () {}
    HCN (int x, int y, int u, int v) : x(x), y(y), u(u), v(v) {}
}rect[N];

struct Doan {
    int x, l, r;
    bool open;
    Doan () {}
    Doan (int x, int l, int r, bool open) : x(x), l(l), r(r), open(open) {}
    bool operator < (const Doan &b) {return x < b.x;}
    void print() {
        cerr << x << ' ' << l << ' ' << r << ' ' << open << endl;
    }
}Line[2*N];

struct edge {
    int x, y, w;
    edge () {}
    edge (int x, int y, int w) : x(x), y(y), w(w) {}
    bool operator < (const edge &b) {return w < b.w;};
}e[2*N];

struct Tree {
    int lazy[12*N], L[12*N], H[12*N];
    long s[12*N];

    void Build(int x, int low, int high) {
        L[x] = low;
        H[x] = high;
        s[x] = lazy[x] = 0;
        if (low < high) {
            int mid = (low + high) / 2;
            Build(2*x, low, mid);
            Build(2*x+1, mid+1, high);
        }
    }

    void Down(int x) {
        int w = lazy[x];
        lazy[2*x] += w;
        lazy[2*x+1] += w;
        s[2*x] += 1ll * w * (H[2*x] - L[2*x] + 1);
        s[2*x+1] += 1ll * w * (H[2*x+1] - L[2*x+1] + 1);
        lazy[x] = 0;
    }

    void Update(int x, int i, int j, int w) {
        if (L[x] > j || H[x] < i) return;
        if (i <= L[x] && H[x] <= j) {
            s[x] += 1ll * w * (H[x] - L[x] + 1);
            lazy[x] += w;
            return;
        }
        Down(x);
        Update(2*x, i, j, w);
        Update(2*x+1, i, j, w);
        s[x] = s[2*x] + s[2*x+1];
    }

    long Query(int x, int i, int j) {
        if (L[x] > j || H[x] < i) return 0;
        if (i <= L[x] && H[x] <= j) return s[x];
        Down(x);
        return Query(2*x, i, j) + Query(2*x+1, i, j);
    }
}it;

struct Quest {
    int w, cnt, id;
    Quest () {}
    bool operator < (const Quest &b) {return w < b.w;}
}q[maxQ];

int n, m, Q, rankX, rankY, E, lab[N], TPLT;
long ans[maxQ], pre[N];
ii a[N], save[N];
map <int, int> mapX, mapY;
map <ii,  int> city;

void Enter() {
    cin >> n >> m >> Q;
    ff(i, 1, n) {
        cin >> a[i].X >> a[i].Y;
        save[i] = a[i];
        city[a[i]] = i;
    }
    ff(i, 1, m) {
        cin >> rect[i].x >> rect[i].y >> rect[i].u >> rect[i].v;
    }
}

void Ranking() {
    mapX.clear();
    mapY.clear();
    ff(i, 1, n) {
        mapX[a[i].X] = 1;
        mapY[a[i].Y] = 1;
    }
    ff(i, 1, m) {
        mapX[rect[i].x] = 1;
        mapX[rect[i].u] = 1;
        mapY[rect[i].y] = 1;
        mapY[rect[i].v] = 1;
    }

    rankX = 0;
    for (map<int, int> :: iterator it = mapX.begin(); it != mapX.end(); ++it) mapX[it->X] = ++rankX;

    rankY = 0;
    for (map<int, int> :: iterator it = mapY.begin(); it != mapY.end(); ++it) mapY[it->X] = ++rankY;
}

void CreateLine() {
    ff(i, 1, m) {
        Line[i] = Doan(mapX[rect[i].x], mapY[rect[i].y], mapY[rect[i].v], 1);
        Line[i+m] = Doan(mapX[rect[i].u], mapY[rect[i].y], mapY[rect[i].v], 0);
    }
    sort(Line+1, Line+1+2*m);
//    ff(i, 1, 2*m) {
//        Love(i); Line[i].print();
//    }
}

void Duyet(int &k, int stop) {
    while (k <= n && mapX[a[k].X] < stop) {
        if (a[k].X == a[k-1].X && it.Query(1, mapY[a[k-1].Y], mapY[a[k].Y]) == 0) {
            e[++E] = edge(city[a[k]], city[a[k-1]], a[k].Y - a[k-1].Y);
        }
        ++k;
    }
}

void BuildEdge() {
    Ranking();
    CreateLine();
    sort(a+1, a+1+n);       //sort cac diem theo x tang dan, x = nhau thi y tang dan
    //ff(i, 1, n) Love(i _ a[i].X _ a[i].Y)

    it.Build(1, 1, rankY);
    int k = 2, j = 1;
    vector <ii> v;
    Duyet(k, Line[1].x);
    Line[2*m+1].x = 1e9 + 7;

    for (int i = 1; i <= 2*m; i = ++j) {
        while (j < 2*m && Line[j+1].x == Line[i].x) ++j;
        ff(z, i, j)
            if (Line[z].open) it.Update(1, Line[z].l, Line[z].r, 1);


        while (k <= n && mapX[a[k].X] == Line[i].x) {
            v.push_back(a[k]);
            ++k;
        }

        ff(z, i, j)
            if (!Line[z].open) it.Update(1, Line[z].l, Line[z].r, -1);

        Duyet(k, Line[j+1].x);

        ff(z, 1, v.size()-1)
            if (!it.Query(1, mapY[v[z-1].Y], mapY[v[z].Y])) {
                e[++E] = edge(city[v[z]], city[v[z-1]], v[z].Y - v[z-1].Y);
            }

        v.clear();
    }
}

void Reverse() {
    city.clear();
    ff(i, 1, n) {
        swap(a[i].X , a[i].Y);
        swap(save[i].X, save[i].Y);
        city[save[i]] = i;
    }
    ff(i, 1, m) {
        swap(rect[i].x, rect[i].y);
        swap(rect[i].u, rect[i].v);
    }
}

int FindSet(int u) {
    return lab[u] < 0 ? u : lab[u] = FindSet(lab[u]);
}

void Union(int r, int s) {
    --TPLT;
    if (lab[r]  < lab[s]) swap(r, s);
    if (lab[r] == lab[s]) lab[s]--;
    lab[r] = s;
}

void Answer() {
    sort(e+1, e+1+E);

//    ff(i, 1, Q) {
//        cin >> q[i].w >> q[i].cnt;
//        q[i].id = i;
//    }
//
//    sort(q+1, q+1+Q);
    fill_n(lab, n+1, -1);
    TPLT = n;
    vector <int> v;
    long res = 0;
    ff(i, 1, E) {
        int r = FindSet(e[i].x), s = FindSet(e[i].y);
        if (r != s) {
            Union(r, s);
            res += e[i].w;
            v.push_back(e[i].w);
        }
    }

    int top = v.size();
    REP(i, top) pre[i] = (i == 0 ? v[i] : pre[i-1] + v[i]);


    ff(i, 1, Q) {
        int w, cnt;
        cin >> w >> cnt;
        if (cnt < TPLT) cout << -1;
        else {
            //if (v.back() <= w) cout << pre[top-1] + 1ll * w * TPLT << endl;
            int x = v.end() - upper_bound(ALL(v), w);
            int can = min(cnt - TPLT, x);
            long ans = (can == top ? 0 : pre[top-can-1]) + 1ll * (can + TPLT) * w;
            cout << ans << endl;
        }
    }
}

void Process() {
    BuildEdge();
    Reverse();
    BuildEdge();
    //ff(i, 1, E) Love(e[i].x _ e[i].y _ e[i].w)
    Answer();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen(NAME".inp", "r", stdin);
    //freopen(NAME".out", "w", stdout);
    Enter();
    Process();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30