Submission #86613

#	Time	Username	Problem	Language	Result	Execution time	Memory
86613		long10024070	도로 건설 사업 (JOI13_construction)	C++11	0 / 100	1064 ms	118752 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 maxsz = 2e5 * 4;
const long long maxn = 2e5;
long long n,m,c,x[maxn],y[maxn],p[maxn],q[maxn],r[maxn],s[maxn],Truex[maxsz],Truey[maxsz];
long long node[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;

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 Update(long long i, long long d)
{
    for (;i<maxsz;i+=i&-i) {
        node[i] += d;
//        cout << i << ' ' << node[i] << "   " ;
    }
//    cout << '\n';
}

long long Query(long long i)
{
    long long res = 0;
//    cout << i << '\n';
    for (;i>0;i&=(i-1)) {
        res += node[i];
//        cout << i << ' ' << node[i] << "   " ;
    }
//    cout << '\n';
    return res;
}

long long QuerySum(long long l, long long r)
{
//    cout << l << ' ' << r << ' ' << Query(r) << ' ' << Query(l-1) << '\n';
    return Query(r) - Query(l-1);
}

void BuildGraph()
{
    for (long long Y=1;Y<maxsz;++Y) {
        add[Y].clear();
        sub[Y].clear();
        mem[Y].clear();
    }
    fill(node,node+maxsz,0);
    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]) {
//            cout << p[i] << ' ' << r[i] << " +1" << '\n';
            Update(p[i],+1);
//            Update(r[i]+1,-1);
        }
        for (long long i : sub[Y]) {
//            cout << p[i] << ' ' << r[i] << " -1" << '\n';
            Update(p[i],-1);
//            Update(r[i]+1,+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 (QuerySum(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 = max(n2 - h, 1ll);
            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;
            }
            cout << chose[r] + 1ll * b * (n - r) << '\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:114: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