Submission #13061

#	Time	Username	Problem	Language	Result	Execution time	Memory
13061		gs14004	도로 건설 사업 (JOI13_construction)	C++14	0 / 100	1077 ms	262144 KiB

construction

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;

int n,m,c;
int x[200005], y[200005];

struct point{
    int x,y,num;
};

bool cmp1(point a, point b){return a.x != b.x ? (a.x < b.x) : (a.y < b.y);}
bool cmp2(point a, point b){return a.y != b.y ? (a.y < b.y) : (a.x < b.x);}

struct edge_hori{
    int sx, ex, y;
    int s,e;
};

struct edge_vert{
    int sy, ey, x;
    int s,e;
};

struct kill_hori{
    int y, sx, ex, dx;
};

struct kill_vert{
    int x, sy, ey, dx;
};

bool cmp3(edge_hori a, edge_hori b){return a.y < b.y;}
bool cmp4(edge_vert a, edge_vert b){return a.x < b.x;}
bool cmp5(kill_hori a, kill_hori b){return a.y < b.y;}
bool cmp6(kill_vert a, kill_vert b){return a.x < b.x;}

struct node{
    node(){
        sum = 0, lazy = 0;
        ls = rs = NULL;
    }
    long long sum, lazy;
    node *ls, *rs;
}*root;

void lazydown(int ps, int pe, node *p){
    if(!p->ls) p->ls = new node();
    if(!p->rs) p->rs = new node();
    if(p->lazy == 0) return;
    p->ls->lazy += p->lazy;
    p->rs->lazy += p->lazy;
    int pm = (ps+pe)/2;
    p->ls->sum += p->lazy * (pm - ps + 1);
    p->rs->sum += p->lazy * (pe - pm);
    p->lazy = 0;
}

void add(int s, int e, int x, int ps, int pe, node *p){
    if(e < ps || pe < s) return;
    if(s <= ps && pe <= e){
        p->sum += (pe - ps + 1) * x;
        p->lazy += x;
        return;
    }
    lazydown(ps,pe,p);
    int pm = (ps+pe)/2;
    add(s,e,x,ps,pm,p->ls);
    add(s,e,x,pm+1,pe,p->rs);
    p->sum = p->ls->sum + p->rs->sum;
}

long long sum(int s, int e, int ps, int pe, node *p){
    if(e < ps || pe < s) return 0;
    if(s <= ps && pe <= e) return p->sum;
    lazydown(ps,pe,p);
    int pm = (ps+pe)/2;
    return sum(s,e,ps,pm,p->ls) + sum(s,e,pm+1,pe,p->rs);
}

vector<edge_hori> eh;
vector<edge_vert> ev;
vector<kill_hori> kh;
vector<kill_vert> kv;

void initialize(){
    point hor[200005];
    point vert[200005];
    scanf("%d %d %d",&n,&m,&c);
    for (int i=0; i<n; i++) {
        scanf("%d %d",&x[i],&y[i]);
    }
    for (int i=0; i<n; i++) {
        hor[i] = {x[i],y[i],i};
        vert[i] = {x[i],y[i],i};
    }
    sort(hor,hor+n,cmp2);
    sort(vert,vert+n,cmp1);
    for (int i=0; i<n-1; i++) {
        if(hor[i].y == hor[i+1].y){
            eh.push_back({hor[i].x,hor[i+1].x,hor[i].y,hor[i].num,hor[i+1].num});
        }
    }
    for (int i=0; i<n-1; i++) {
        if(vert[i].x == vert[i+1].x){
            ev.push_back({vert[i].y,vert[i+1].y,vert[i].x,vert[i].num,vert[i+1].num});
        }
    }
    for (int i=0; i<m; i++) {
        int p,q,r,s;
        scanf("%d %d %d %d",&p,&q,&r,&s);
        kh.push_back({q,p,r,1});
        kh.push_back({s+1,p,r,-1});
        kv.push_back({p,q,s,1});
        kv.push_back({r+1,q,s,-1});
    }
    sort(eh.begin(),eh.end(),cmp3);
    sort(ev.begin(),ev.end(),cmp4);
    sort(kh.begin(),kh.end(),cmp5);
    sort(kv.begin(),kv.end(),cmp6);
}

struct edge{int s,e,x;};
bool cmp7(edge a, edge b){return a.x < b.x;}

vector<edge> ret_edge;

void graph_retrieval(){
    root = new node();
    int p1 = 0, p2 = 0;
    while (p1 < eh.size() && p2 < kh.size()) {
        if(eh[p1].y < kh[p2].y){
            if(sum(eh[p1].sx,eh[p1].ex,0,1e9,root) == 0){
                ret_edge.push_back({eh[p1].s,eh[p1].e,eh[p1].ex - eh[p1].sx});
            }
            p1++;
        }
        else{
            add(kh[p2].sx,kh[p2].ex,kh[p2].dx,0,1e9,root);
            p2++;
        }
    }
    while (p1 < eh.size()) {
        ret_edge.push_back({eh[p1].s,eh[p1].e,eh[p1].ex - eh[p1].sx});
        p1++;
    }
    root = new node();
    p1 = 0, p2 = 0;
    while (p1 < ev.size() && p2 < kv.size()) {
        if(ev[p1].x < kv[p2].x){
            if(sum(ev[p1].sy,ev[p1].ey,0,1e9,root) == 0){
                ret_edge.push_back({ev[p1].s,ev[p1].e,ev[p1].ey - ev[p1].sy});
            }
            p1++;
        }
        else{
            add(kv[p2].sy,kv[p2].ey,kv[p2].dx,0,1e9,root);
            p2++;
        }
    }
    while (p1 < ev.size()) {
        ret_edge.push_back({ev[p1].s,ev[p1].e,ev[p1].ey - ev[p1].sy});
        p1++;
    }
}

struct disj{
    int pa[200005], r[200005];
    void init(int n){
        for(int i=0; i<=n; i++){
            pa[i] = i;
        }
    }
    int find(int x){
        if(pa[x] == x) return x;
        return pa[x] = find(pa[x]);
    }
    bool uni(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return 0;
        if(r[x] < r[y]) pa[y] = x;
        else pa[x] = y;
        if(r[x] == r[y]) r[x]++;
        return 1;
    }
}disj;

vector<int> ret;
vector<long long> psum;

void tree_retrieval(){
    disj.init(n);
    sort(ret_edge.begin(),ret_edge.end(),cmp7);
    for(edge i : ret_edge){
        if(disj.uni(i.s,i.e)){
            ret.push_back(i.x);
            psum.push_back(i.x + (psum.empty() ? 0 : psum.back()));
        }
    }
}

inline long long get_sum(int x){
    if(x == 0) return 0;
    return psum[x-1];
}

void process_query(){
    while (c--) {
        int b,k;
        scanf("%d %d",&b,&k);
        k = min(k,n);
        if(k + ret.size() < n) puts("-1");
        else{
            auto x = upper_bound(ret.begin(),ret.end(),b);
            int cnt = (int)(x - ret.begin());
            if(cnt + k < n){
                printf("%lld\n",get_sum(n-k) + 1ll * b * k);
            }
            else{
                printf("%lld\n",get_sum(cnt) + 1ll * (n - cnt) * b);
            }
        }
    }
}

int main(){
    initialize();
    graph_retrieval();
    tree_retrieval();
    process_query();
}

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