Submission #283921

#	Time	Username	Problem	Language	Result	Execution time	Memory
283921		mhy908	도로 건설 사업 (JOI13_construction)	C++14	100 / 100	2411 ms	131552 KiB

construction

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
const LL llinf=2e18;

int n, m, q;
pair<pii, int> p[200010];
pair<pii, pii> rct[200010];
pair<pil, int> qu[500010];

vector<int> idx, idy;
int tox[600010], toy[600010];
void compress_grid(){
    svec(idx); svec(idy);
    press(idx); press(idy);
    for(int i=1; i<=n; i++){
        int tmp=lower_bound(all(idx), p[i].F.F)-idx.begin()+1;
        tox[tmp]=p[i].F.F;
        p[i].F.F=tmp;
        tmp=lower_bound(all(idy), p[i].F.S)-idy.begin()+1;
        toy[tmp]=p[i].F.S;
        p[i].F.S=tmp;
    }
    for(int i=1; i<=m; i++){
        int tmp=lower_bound(all(idx), rct[i].F.F)-idx.begin()+1;
        tox[tmp]=rct[i].F.F;
        rct[i].F.F=tmp;
        tmp=lower_bound(all(idx), rct[i].S.F)-idx.begin()+1;
        tox[tmp]=rct[i].S.F;
        rct[i].S.F=tmp;
        tmp=lower_bound(all(idy), rct[i].F.S)-idy.begin()+1;
        toy[tmp]=rct[i].F.S;
        rct[i].F.S=tmp;
        tmp=lower_bound(all(idy), rct[i].S.S)-idy.begin()+1;
        toy[tmp]=rct[i].S.S;
        rct[i].S.S=tmp;
    }
}

struct SEGMENT_TREE{
    LL tree[2400010], lazy[2400010];
    void prop(int point, int s, int e){
        tree[point]+=lazy[point]*(e-s+1);
        if(s!=e){
            lazy[point*2]+=lazy[point];
            lazy[point*2+1]+=lazy[point];
        }
        lazy[point]=0;
    }
    void eat(int point, int s, int e){
        int mid=(s+e)/2;
        tree[point]=tree[point*2]+tree[point*2+1];
        tree[point]+=lazy[point*2]*(mid-s+1);
        tree[point]+=lazy[point*2+1]*(e-mid);
    }
    void alter(int point, int s, int e, int a, int b, LL val){
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            lazy[point]+=val;
            return;
        }
        prop(point, s, e);
        alter(point*2, s, (s+e)/2, a, b, val);
        alter(point*2+1, (s+e)/2+1, e, a, b, val);
        eat(point, s, e);
    }
    LL query(int point, int s, int e, int a, int b){
        if(e<a||s>b)return 0;
        if(a<=s&&e<=b)return tree[point]+lazy[point]*(e-s+1);
        prop(point, s, e);
        LL ret=0;
        ret+=query(point*2, s, (s+e)/2, a, b);
        ret+=query(point*2+1, (s+e)/2+1, e, a, b);
        eat(point, s, e);
        return ret;
    }
    void cl(){
        memset(tree, 0, sizeof tree);
        memset(lazy, 0, sizeof lazy);
    }
}seg;
int e;
pair<LL, pii> edg[400010];

vector<pii> vc[600010], upd[600010];
inline void make_edge_x(){
    sort(p+1, p+n+1);
    for(int i=1; i<=n+2*m; i++){
        vc[i].clear();
        upd[i].clear();
    }
    seg.cl();
    for(int i=2; i<=n; i++){
        if(p[i-1].F.F==p[i].F.F)vc[p[i].F.F].eb(i-1, i);
    }
    for(int i=1; i<=m; i++){
        upd[rct[i].F.F].eb(rct[i].F.S, rct[i].S.S);
        upd[rct[i].S.F+1].eb(-rct[i].F.S, -rct[i].S.S);
    }
    for(int i=1; i<=n+2*m; i++){
        for(auto j:upd[i]){
            if(j.F>0)seg.alter(1, 1, n+2*m, j.F, j.S, 1);
            else seg.alter(1, 1, n+2*m, -j.F, -j.S, -1);
        }
        for(auto j:vc[i]){
            LL tmp=seg.query(1, 1, n+2*m, p[j.F].F.S, p[j.S].F.S);
            if(tmp!=0)continue;
            edg[++e]=mp((LL)(toy[p[j.S].F.S]-toy[p[j.F].F.S]), mp(p[j.F].S, p[j.S].S));
        }
    }
}

bool cmp(pair<pii, int> a, pair<pii, int> b){
    return mp(a.F.S, a.F.F)<mp(b.F.S, b.F.F);
}
inline void make_edge_y(){
    sort(p+1, p+n+1, cmp);
    for(int i=1; i<=n+2*m; i++){
        vc[i].clear();
        upd[i].clear();
    }
    seg.cl();
    for(int i=2; i<=n; i++){
        if(p[i-1].F.S==p[i].F.S)vc[p[i].F.S].eb(i-1, i);
    }
    for(int i=1; i<=m; i++){
        upd[rct[i].F.S].eb(rct[i].F.F, rct[i].S.F);
        upd[rct[i].S.S+1].eb(-rct[i].F.F, -rct[i].S.F);
    }
    for(int i=1; i<=n+2*m; i++){
        for(auto j:upd[i]){
            if(j.F>0)seg.alter(1, 1, n+2*m, j.F, j.S, 1);
            else seg.alter(1, 1, n+2*m, -j.F, -j.S, -1);
        }
        for(auto j:vc[i]){
            LL tmp=seg.query(1, 1, n+2*m, p[j.F].F.F, p[j.S].F.F);
            if(tmp!=0)continue;
            edg[++e]=mp((LL)(tox[p[j.S].F.F]-tox[p[j.F].F.F]), mp(p[j.F].S, p[j.S].S));
        }
    }
}

LL mst[200010];
struct UNION_FIND{
    int par[200010];
    UNION_FIND(){for(int i=1; i<=200000; i++)par[i]=i;}
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}uf;
inline void make_mst(){
    sort(edg+1, edg+e+1);
    for(int i=1; i<=n-1; i++)mst[i]=llinf;
    int num=n;
    for(int i=1; i<=e; i++){
        int a=edg[i].S.F, b=edg[i].S.S;
        if(uf.findpar(a)==uf.findpar(b))continue;
        num--;
        uf.mergepar(a, b);
        mst[num]=mst[num+1]+edg[i].F;
    }
}

struct DYNAMIC_LI_CHAO{
    struct NODE {
        LL st, fin;
        LL a, b;
        NODE *l, *r;
        NODE(){st=fin=a=0, b=llinf; l=r=0;}
    }*root;
    LL getfx(NODE* nd, LL num){
        if(num<=(nd->fin+nd->st)/2)return min(nd->a*num+nd->b, nd->l?getfx(nd->l, num):llinf);
        return min(nd->a*num+nd->b, nd->r?getfx(nd->r, num):llinf);
    }
    void in_LICHAO(NODE* nd, LL aa, LL bb){
        LL mid=(nd->fin+nd->st)/2;
        LL fr=nd->a*nd->st+nd->b;
        LL re=nd->a*nd->fin+nd->b;
        LL nfr=aa*nd->st+bb;
        LL nre=aa*nd->fin+bb;
        if(fr<=nfr&&re<=nre)return;
        if(fr>=nfr&&re>=nre){
            nd->a=aa;
            nd->b=bb;
            return;
        }
        if(!nd->l){
            nd->l=new NODE;
            nd->l->st=nd->st;
            nd->l->fin=mid;
        }
        if(!nd->r){
            nd->r=new NODE;
            nd->r->st=mid+1;
            nd->r->fin=nd->fin;
        }
        in_LICHAO(nd->l, aa, bb);
        in_LICHAO(nd->r, aa, bb);
    }
    LL getfx(LL a){return getfx(root, a);}
    void in(LL a, LL b){in_LICHAO(root, a, b);}
    DYNAMIC_LI_CHAO(){root=new NODE; root->st=1ll, root->fin=1000000000ll;}
}li;
LL ans[500010];
inline void cht(){
    sort(qu+1, qu+q+1);
    int pv=1;
    for(int i=1; i<=q; i++){
        for(; pv<=n; pv++){
            if(pv>qu[i].F.F)break;
            li.in((LL)pv, mst[pv]);
        }
        ans[qu[i].S]=li.getfx(qu[i].F.S);
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &p[i].F.F, &p[i].F.S);
        idx.eb(p[i].F.F);
        idy.eb(p[i].F.S);
        p[i].S=i;
    }
    for(int i=1; i<=m; i++){
        scanf("%d %d %d %d", &rct[i].F.F, &rct[i].F.S, &rct[i].S.F, &rct[i].S.S);
        idx.eb(rct[i].F.F);
        idx.eb(rct[i].S.F);
        idy.eb(rct[i].F.S);
        idy.eb(rct[i].S.S);
    }
    for(int i=1; i<=q; i++){
        scanf("%lld %d", &qu[i].F.S, &qu[i].F.F);
        qu[i].S=i;
    }
    compress_grid();
    make_edge_x();
    make_edge_y();
    make_mst();
    cht();
    for(int i=1; i<=q; i++)printf("%lld\n", ans[i]>=llinf?-1:ans[i]);
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:226:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  226 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:228:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  228 |         scanf("%d %d", &p[i].F.F, &p[i].F.S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:234:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  234 |         scanf("%d %d %d %d", &rct[i].F.F, &rct[i].F.S, &rct[i].S.F, &rct[i].S.S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:241:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  241 |         scanf("%lld %d", &qu[i].F.S, &qu[i].F.F);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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