Submission #35253

#	Time	Username	Problem	Language	Result	Execution time	Memory
35253		bql20000	도로 건설 사업 (JOI13_construction)	C++14	100 / 100	1018 ms	40380 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 gc getchar
#define pc putchar

#define NAME            "Construction"

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

inline void read(int &x){
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(long x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }

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 city {
    int x, y, id;
    city () {}
    bool operator < (const city &b) {
        return x < b.x || x == b.x && y < b.y;
    }
}a[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];


int n, m, Q, rankX, rankY, E, lab[N], TPLT;
long pre[N];

void Enter() {
    read(n);  read(m);  read(Q);

    ff(i, 1, n) {
        read(a[i].x); read(a[i].y);
        a[i].id = i;
    }
    ff(i, 1, m) {
        read(rect[i].x);
        read(rect[i].y);
        read(rect[i].u);
        read(rect[i].v);
    }
}

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

multiset<int> st;

void BuildEdge() {
    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)

    st.clear();
    int k = 1;
    ff(i, 2, n)
        if (a[i].x == a[i-1].x) {
            for(; k <= 2*m && Line[k].x <= a[i].x; ++k) {
                if (Line[k].open) {
                    st.insert(Line[k].l);
                    st.insert(Line[k].r);
                }
                else {
                    st.erase(st.find(Line[k].l));
                    st.erase(st.find(Line[k].r));
                }
            }

            multiset<int> :: iterator it = st.lower_bound(a[i-1].y);
            if (it == st.end() || (*it) > a[i].y) {
                e[++E] = edge(a[i].id, a[i-1].id, a[i].y - a[i-1].y);
            }
        }
}

void Reverse() {
    ff(i, 1, n) {
        swap(a[i].x , a[i].y);
    }
    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);

    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;
        read(w); read(cnt);
        if (cnt < TPLT) writeln(-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;
            writeln(ans);
        }
    }
}

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;
}

Compilation message (stderr)

construction.cpp: In member function 'bool city::operator<(const city&)':
construction.cpp:57:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return x < b.x || x == b.x && y < b.y;
                                    ^

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