Submission #35343

#	Time	Username	Problem	Language	Result	Execution time	Memory
35343		wan2000	도로 건설 사업 (JOI13_construction)	C++14	100 / 100	1766 ms	83880 KiB

construction

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

template<typename T> inline void read(T &x){
    x = 0; char ch;
    while(!isdigit(ch=getchar()));
    do{x=10*x+ch-'0';}while(isdigit(ch=getchar()));
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x); putchar('\n');
}

typedef long long ll;

const int N = 2e5+111;

int n, m, k, pos[3*N], num, cnt, ID[3*N], Fa[N], eNum;
ll D[3*N], F[N];

struct pt{
    int x, y;
    ll rx, ry;
    pt(){}
    pt(int a, int b){
        x = a; y = b;
        rx = (ll)x; ry = (ll)y;
    }
} P[3*N];

struct data{
    int x;
    int y, l, r;
    int type, id;
    ll rx;
    data(){}
    data(int a, int b, int c, int d, int e, int f){
        x = a; y = b; l = c; r = d; type = e; id = f;
    }
};
vector<data> T;

struct Edge{
    int u, v;
    ll w;
    Edge(){}
    Edge(int a, int b, ll c){
        u = a; v = b; w = c;
    }
} E[4*N];

bool cmp_x(int a, int b){
    return P[a].x < P[b].x;
}

bool cmp_y(int a, int b){
    return P[a].y < P[b].y;
}

bool operator < (const data &a, const data &b){
    return a.x < b.x || (a.x==b.x&&a.type<b.type);
}

bool operator < (const Edge &a, const Edge &b){
    return a.w < b.w;
}

void compress(){
    num = n+2*m;
    for(int i = 1; i <= num; i++){
        pos[i] = i;
    }
    sort(pos+1,pos+num+1,cmp_x);
    cnt = 1;
    int cur = P[pos[1]].x;
    P[pos[1]].x = 1;
    for(int i = 2; i <= num; i++){
        if(P[pos[i]].x!=cur){
            cnt++;
            cur = P[pos[i]].x;
        }
        P[pos[i]].x = cnt;
    }
    sort(pos+1,pos+num+1,cmp_y);
    cnt = 1;
    cur = P[pos[1]].y;
    P[pos[1]].y = 1;
    for(int i = 2; i <= num; i++){
        if(P[pos[i]].y!=cur){
            cnt++;
            cur = P[pos[i]].y;
        }
        P[pos[i]].y = cnt;
    }
}

struct SegTree{
    int ST[12*N], Lazy[12*N];
    void reset(){
        memset(ST,255,sizeof(ST));
        memset(Lazy,255,sizeof(Lazy));
    }
    void down(int id, int l, int r){
        if(Lazy[id]==-1) return;
        ST[id] = max(ST[id],Lazy[id]);
        if(l!=r){
            Lazy[2*id] = max(Lazy[2*id],Lazy[id]);
            Lazy[2*id+1] = max(Lazy[2*id+1],Lazy[id]);
        }
        Lazy[id] = -1;
    }
    void upgrade(int id, int l, int r, int u, int v, int val){
        down(id,l,r);
        if(r<u||v<l) return;
        if(u<=l&&r<=v){
            Lazy[id] = max(Lazy[id],val);
            down(id,l,r);
            return;
        }
        int mid = (l+r)>>1;
        upgrade(2*id,l,mid,u,v,val);
        upgrade(2*id+1,mid+1,r,u,v,val);
        ST[id] = ST[2*id]+ST[2*id+1];
    }
    int get(int id, int l, int r, int x){
        down(id,l,r);
        if(x<l||r<x) return -1;
        if(l==r) return ST[id];
        int mid = (l+r)>>1;
        return max(get(2*id,l,mid,x),get(2*id+1,mid+1,r,x));
    }
} Tree;

void makeGraph(){
    sort(T.begin(),T.end());
    memset(D,255,sizeof(D));
    Tree.reset();
    for(int i = 0; i < (int)T.size(); i++){
        data dt = T[i];
        if(dt.type==0) Tree.upgrade(1,1,num,dt.l,dt.r,dt.x);
        else{
            if(D[dt.y]==-1){
                D[dt.y] = dt.x;
                ID[dt.y] = dt.id;
            }
            else{
                ll x = (ll)Tree.get(1,1,num,dt.y);
                int id = ID[dt.y];
                ll xx = D[dt.y];
                if(xx>x){
                    E[++eNum] = Edge(dt.id,id,abs(xx-dt.x));
                }
                D[dt.y] = dt.x;
                ID[dt.y] = dt.id;
            }
        }
    }
}

int root(int x){
    if(Fa[x]<0) return x;
    int t = root(Fa[x]);
    return Fa[x] = t;
}

void unite(int x, int y){
    if(Fa[x]<Fa[y]){
        Fa[x] += Fa[y];
        Fa[y] = x;
    }
    else{
        Fa[y] += Fa[x];
        Fa[x] = y;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    read(n); read(m); read(k);
    for(int i = 1; i <= n; i++){
        int x, y;
        read(x); read(y);
        P[i] = pt(x,y);
    }
    for(int i = 1; i < 2*m; i+=2){
        int a, b, c, d;
        read(a); read(b); read(c); read(d);
        P[n+i] = pt(a,b);
        P[n+i+1] = pt(c,d);
    }
    compress();
    for(int i = 1; i <= n; i++){
        T.push_back(data(P[i].rx,P[i].y,0,0,1,i));
    }
    for(int i = 1; i < 2*m; i+=2){
        //T.push_back(data(B[i].up.x,0,B[i].up.y,B[i].down.y,0,0,0));
        T.push_back(data(P[i+n+1].rx,0,P[i+n].y,P[i+n+1].y,0,0));
    }
    makeGraph();
    T.clear();
    for(int i = 1; i <= n; i++){
        T.push_back(data(P[i].ry,P[i].x,0,0,1,i));
    }
    for(int i = 1; i < 2*m; i+=2){
        //T.push_back(data(B[i].up.y,0,B[i].up.x,B[i].down.x,0,0,0));
        T.push_back(data(P[i+n+1].ry,0,P[i+n].x,P[i+n+1].x,0,0));
    }
    makeGraph();
    sort(E+1,E+eNum+1);
    memset(Fa,255,sizeof(Fa));
    int com = n;
    ll sum = 0;
    for(int i = 1; i <= eNum; i++){
        int u = E[i].u;
        int v = E[i].v;
        ll w = E[i].w;
        int ru = root(u);
        int rv = root(v);
        if(ru==rv) continue;
        unite(ru,rv);
        com--;
        sum += w;
        F[com] = sum;
    }
    while(k--){
        ll c;
        int h;
        read(c); read(h);
        if(h<com) writeln(-1);
        else{
            int l = com, r = h;
            int ml = floor((double)(l+l+r)/3);
            int mr = ceil((double)(l+r+r)/3);
            while(ml<mr){
                if(F[ml]+c*(ll)ml<F[mr]+c*(ll)mr) r = mr-1;
                else l = ml+1;
                ml = floor((double)(l+l+r)/3);
                mr = ceil((double)(l+r+r)/3);
            }
            ll res = F[ml]+c*(ll)ml;
            writeln(res);
        }
    }
    return 0;
}

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