제출 #361321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361321		Lam_lai_cuoc_doi	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	1882 ms	95084 KiB

construction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 2e5 + 5;
struct Edge
{
    int u, v;
    ll w;
    Edge(const int &u = 0, const int &v = 0, const ll &w = 0) : u(u), v(v), w(w)
    {
    }
    bool operator<(const Edge &a) const
    {
        return w < a.w;
    }
};
struct FenwickTree
{
    vector<ll> a;
    int n;
    FenwickTree(const int &n = 0)
    {
        a.resize(n + 1);
        this->n = n;
    }
    void Clear()
    {
        fill(a.begin(), a.end(), 0);
    }
    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    ll Get(int p)
    {
        ll ans(0);
        for (; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }
    ll Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
};
struct RangeFen
{
    FenwickTree s1, s2;
    int n;
    RangeFen(const int &n = 0)
    {
        this->n = n;
        s1 = FenwickTree(n);
        s2 = FenwickTree(n);
    }
    void Clear()
    {
        s1.Clear();
        s2.Clear();
    }
    void Update(int l, int r, ll v)
    {
        s1.Update(l, v);
        s1.Update(r + 1, -v);
        s2.Update(l, (l - 1) * v);
        s2.Update(r + 1, -v * r);
    }
    ll Get(int p)
    {
        return s1.Get(p) * p - s2.Get(p);
    }
    ll Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} f;
struct dsu
{
    int par[N];
    dsu()
    {
        memset(par, -1, sizeof par);
    }
    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }
    bool merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);
        if (u == v)
            return false;
        if (par[u] < par[v])
            swap(u, v);
        par[v] += par[u];
        par[u] = v;
        return true;
    }
} g;
int n, m, c;
int u[N], v[N], p[N], q[N], r[N], s[N];
vector<int> x, y;
vector<ll> ans, res;
vector<vector<int>> pos;
vector<vector<pair<int, int>>> in, out;
vector<Edge> e;

void Read()
{
    cin >> n >> m >> c;
    x.reserve(m * 2 + n);
    y.reserve(m * 2 + n);
    for (int i = 1; i <= n; ++i)
    {
        cin >> u[i] >> v[i];
        x.push_back(u[i]);
        y.push_back(v[i]);
    }
    for (int i = 1; i <= m; ++i)
    {
        cin >> p[i] >> q[i] >> r[i] >> s[i];
        x.push_back(p[i]);
        x.push_back(r[i]);
        y.push_back(q[i]);
        y.push_back(s[i]);
    }
}

void Sort(vector<int> &s)
{
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
}

int Find(vector<int> &s, int v)
{
    return lower_bound(s.begin(), s.end(), v) - s.begin();
}

void Sort_pos()
{
    for (int i = 0; i < (int)pos.size(); ++i)
        sort(pos[i].begin(), pos[i].end(), [&](const int &x, const int &y) {
            return v[x] < v[y];
        });
}

void Prog(int sz, vector<int> &y)
{
    for (int i = 0; i < (int)sz; ++i)
    {
        for (auto j : in[i])
            f.Update(Find(y, j.first) + 1, Find(y, j.second), 1);
        for (int j = 0; j < (int)pos[i].size(); ++j)
        {
            int t = j + 1;
            while (t < (int)pos[i].size() && f.Get(Find(y, v[pos[i][j]]) + 1, Find(y, v[pos[i][t]])) == 0)
            {
                e.emplace_back(pos[i][t], pos[i][t - 1], v[pos[i][t]] - v[pos[i][t - 1]]);
                ++t;
            }
            j = t - 1;
        }
        for (auto j : out[i])
            f.Update(Find(y, j.first) + 1, Find(y, j.second), -1);
    }
}

void Kruskal()
{
    sort(e.begin(), e.end());
    ans.reserve((int)e.size() + 1);
    ans.push_back(0);
    for (auto i : e)
        if (g.merge(i.u, i.v)){
            ans.push_back(i.w);
        }
    res.resize(ans.size(), 0);
    for (int i = 1; i < (int)ans.size(); ++i)
        res[i] = res[i - 1] + ans[i];
}

void Solve()
{
    Sort(x);
    Sort(y);
    f = RangeFen((int)max(x.size(), y.size()));
    pos.resize(max(x.size(), y.size()));
    in.resize(max(x.size(), y.size()));
    out.resize(max(x.size(), y.size()));
    for (int i = 1; i <= n; ++i)
        pos[Find(x, u[i])].push_back(i);
    Sort_pos();
    for (int i = 1; i <= m; ++i)
    {
        in[Find(x, p[i])].push_back({q[i], s[i]});
        out[Find(x, r[i])].push_back({q[i], s[i]});
    }
    Prog(x.size(), y);
    for (int i = 0; i < (int)x.size(); ++i)
    {
        pos[i].clear();
        in[i].clear();
        out[i].clear();
    }
    for (int i = 1; i <= n; ++i)
    {
        pos[Find(y, v[i])].push_back(i);
        swap(u[i], v[i]);
    }
    Sort_pos();
    for (int i = 1; i <= m; ++i)
    {
        in[Find(y, q[i])].push_back({p[i], r[i]});
        out[Find(y, s[i])].push_back({p[i], r[i]});
    }
    Prog(y.size(), x);
    Kruskal();
    while (c--)
    {
        int k;
        ll b;
        cin >> b >> k;
        if (k < n - (int)ans.size() + 1)
        {
            cout << "-1\n";
            continue;
        }
        k -= n - ans.size() + 1;
        int j = max((int)(lower_bound(ans.begin() + 1, ans.end(), b) - ans.begin()), (int)ans.size() - k);
        cout << res[j - 1] + b * (ans.size() - j) + (n - ans.size() + 1) * b << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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