Submission #86644

#	Time	Username	Problem	Language	Result	Execution time	Memory
86644		long10024070	도로 건설 사업 (JOI13_construction)	C++11	0 / 100	2476 ms	141436 KiB

construction

#define Link "https://dunjudge.me/analysis/problems/980/?fbclid=IwAR0lz5NJ1ferKp5nADDwgoLiHvUbIE48RZqI5DtvPEqUlf-6RFpMV2Thm_c"

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define TASK "Construction Project"

using namespace std;

const long long maxn = 2e5;
const long long maxsz = maxn * 4;
long long n,m,c,x[maxn],y[maxn],p[maxn],q[maxn],r[maxn],s[maxn],Truex[maxsz],Truey[maxsz];
vector <long long> add[maxsz],sub[maxsz],mem[maxsz];
long long cntedge,u[maxsz],v[maxsz],w[maxsz],id[maxsz];
long long lab[maxsz];
vector <long long> chose;
struct T_node
{
    int l,r,val,lazy;
} node[maxsz*6];

void Enter()
{
    cin >> n >> m >> c;
    for (long long i=1;i<=n;++i)
        cin >> x[i] >> y[i];
    for (long long i=1;i<=m;++i)
        cin >> p[i] >> q[i] >> r[i] >> s[i];
}

void Analyze(long long a[], long long b[], long long c[], long long True[])
{
    vector <long long*> v;
    for (long long i=1;i<=n;++i)
        v.push_back(&a[i]);
    for (long long i=1;i<=m;++i)
        v.push_back(&b[i]);
    for (long long i=1;i<=m;++i)
        v.push_back(&c[i]);
    sort(v.begin(),v.end(),
         [] (long long *i, long long *j)
         {
             return *i < *j;
         });
    long long cnt = 0;
    long long pre = -1;
    for (auto p : v) {
        if (*p != pre) {
            ++cnt;
//            cout << *p << ' ';
            True[cnt] = pre = *p;
        }
        *p = cnt;
    }
//    cout << '\n' << '\n';;
}

void Build_tree(int i, int l, int r)
{
    node[i].l = l;
    node[i].r = r;
    node[i].val = 0;
    node[i].lazy = 0;
    if (l != r) {
        Build_tree(i*2,l,(l+r)/2);
        Build_tree(i*2+1,(l+r)/2+1,r);
    }
}

void Down_node(int i)
{
    node[i].val += node[i].lazy;
    if (node[i].l != node[i].r) {
        node[i*2].lazy += node[i].lazy;
        node[i*2+1].lazy += node[i].lazy;
    }
    node[i].lazy = 0;
}

void Recal(int i)
{
    Down_node(i*2);
    Down_node(i*2+1);
    node[i].val = max(node[i*2].val,node[i*2+1].val);
}

void Update(int i, int l, int r, int d)
{
    if (r < node[i].l || node[i].r < l)
        return;
    if (l <= node[i].l && node[i].r <= r)
        node[i].lazy += d;
    else {
        Down_node(i);
        Update(i*2,l,r,d);
        Update(i*2+1,l,r,d);
        Recal(i);
    }
}

int Query(int i, int l, int r)
{
    if (r < node[i].l || node[i].r < l)
        return 0;
    Down_node(i);
    if (l <= node[i].l && node[i].r <= r)
        return node[i].val;
    else {
        int res = max(Query(i*2,l,r),Query(i*2+1,l,r));
        Recal(i);
        return res;
    }
}

void BuildGraph()
{
    Build_tree(1,1,maxsz);
    for (long long Y=1;Y<maxsz;++Y) {
        add[Y].clear();
        sub[Y].clear();
        mem[Y].clear();
    }
    for (long long i=1;i<=m;++i) {
        add[q[i]].push_back(i);
        sub[s[i]+1].push_back(i);
    }
    for (long long i=1;i<=n;++i)
        mem[y[i]].push_back(i);
    for (long long Y=1;Y<maxsz;++Y) {
        for (long long i : add[Y])
            Update(1,p[i],r[i],+1);
        for (long long i : sub[Y])
            Update(1,p[i],r[i],-1);
        sort(mem[Y].begin(),mem[Y].end(),
             [] (long long i, long long j)
             {
                 return x[i] < x[j];
             });
        for (long long t=0;t+1<mem[Y].size();++t) {
            long long i1 = mem[Y][t];
            long long i2 = mem[Y][t+1];
//            cout << i1 << ' ' << i2 << ' ' << x[i1] << ' ' << x[i2] << ' ' << Truex[x[i1]] << ' ' << Truex[x[i2]] << ' ' << QuerySum(x[i1],x[i2]) << '\n';
            if (Query(1,x[i1],x[i2]) == 0) {
                ++cntedge;
                u[cntedge] = i1;
                v[cntedge] = i2;
                w[cntedge] = Truex[x[i2]] - Truex[x[i1]];
            }
        }
    }
}

void Init()
{
    Analyze(x,p,r,Truex);
    Analyze(y,q,s,Truey);
    BuildGraph();
    swap(x,y);
    swap(q,p);
    swap(r,s);
    swap(Truex,Truey);
    BuildGraph();
    swap(x,y);
    swap(q,p);
    swap(r,s);
    swap(Truex,Truey);
}

long long Find_set(long long n)
{
    return lab[n] > 0 ? lab[n] = Find_set(lab[n]) : n;
}

bool Union(long long s, long long t)
{
    if (s == t)
        return 0;
    if (lab[s] > lab[t])
        swap(s,t);
    lab[s] += lab[t];
    lab[t] = s;
    return 1;
}

void Solve()
{
    for (long long i=1;i<=cntedge;++i)
        id[i] = i;
    sort(id+1,id+cntedge+1,
         [] (long long i, long long j)
         {
             return w[i] < w[j];
         });
    for (long long t=1;t<=cntedge;++t) {
        long long i = id[t];
        if (Union(Find_set(u[i]),Find_set(v[i]))) {
//            cout << u[i] << ' ' << v[i] << ' ' << w[i] << '\n';
            chose.push_back(w[i]);
        }
    }
    long long n2 = chose.size();
    chose.push_back(0);
    sort(chose.begin(),chose.end());
    for (long long i=1;i<=n2;++i)
        chose[i] += chose[i-1];
    for (long long i=1;i<=c;++i) {
        long long b,h;
        cin >> b >> h;
//        cout << b << ' ' << h << ' ' << n << ' ' << n2 << '\n';
        h -= n - n2;
        if (h >= 0) {
            long long l = 1;
            long long r = n2;
            while (l <= r) {
                long long m = (l + r) / 2;
                if (chose[m] - chose[m-1] < b)
                    l = m + 1;
                else
                    r = m - 1;
            }
            l = max(l-1,n2-h);
            cout << chose[l] + 1ll * b * (n - l) << '\n';
        }
        else
            cout << -1 << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

#ifdef LHL
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
#else
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
#endif // LHL

    Enter();
    Init();
    Solve();
}

Compilation message (stderr)

construction.cpp: In function 'void BuildGraph()':
construction.cpp:141:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (long long t=0;t+1<mem[Y].size();++t) {
                            ~~~^~~~~~~~~~~~~~

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