oj.uz

Submission #283921

# Submission time Handle Problem Language Result Execution time Memory
283921 2020-08-26T09:40:18 Z mhy908 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 2411 ms 131552 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 68344 KB Output is correct
2 Correct 510 ms 93412 KB Output is correct
3 Correct 518 ms 91556 KB Output is correct
4 Correct 495 ms 81120 KB Output is correct
5 Correct 573 ms 107504 KB Output is correct
6 Correct 519 ms 94948 KB Output is correct
7 Correct 397 ms 83936 KB Output is correct
8 Correct 373 ms 83480 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 68344 KB Output is correct
2 Correct 510 ms 93412 KB Output is correct
3 Correct 518 ms 91556 KB Output is correct
4 Correct 495 ms 81120 KB Output is correct
5 Correct 573 ms 107504 KB Output is correct
6 Correct 519 ms 94948 KB Output is correct
7 Correct 397 ms 83936 KB Output is correct
8 Correct 373 ms 83480 KB Output is correct
9 Correct 1980 ms 111132 KB Output is correct
10 Correct 1966 ms 111160 KB Output is correct
11 Correct 1974 ms 111180 KB Output is correct
12 Correct 2074 ms 111168 KB Output is correct
13 Correct 1004 ms 93120 KB Output is correct
14 Correct 558 ms 108132 KB Output is correct
15 Correct 2043 ms 111132 KB Output is correct
16 Correct 855 ms 103428 KB Output is correct
17 Correct 820 ms 103120 KB Output is correct
18 Correct 1171 ms 111488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 68344 KB Output is correct
2 Correct 510 ms 93412 KB Output is correct
3 Correct 518 ms 91556 KB Output is correct
4 Correct 495 ms 81120 KB Output is correct
5 Correct 573 ms 107504 KB Output is correct
6 Correct 519 ms 94948 KB Output is correct
7 Correct 397 ms 83936 KB Output is correct
8 Correct 373 ms 83480 KB Output is correct
9 Correct 918 ms 126392 KB Output is correct
10 Correct 942 ms 128032 KB Output is correct
11 Correct 864 ms 121368 KB Output is correct
12 Correct 849 ms 108228 KB Output is correct
13 Correct 760 ms 112160 KB Output is correct
14 Correct 944 ms 131552 KB Output is correct
15 Correct 938 ms 126100 KB Output is correct
16 Correct 917 ms 124276 KB Output is correct
17 Correct 738 ms 111148 KB Output is correct
18 Correct 820 ms 109840 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 68344 KB Output is correct
2 Correct 510 ms 93412 KB Output is correct
3 Correct 518 ms 91556 KB Output is correct
4 Correct 495 ms 81120 KB Output is correct
5 Correct 573 ms 107504 KB Output is correct
6 Correct 519 ms 94948 KB Output is correct
7 Correct 397 ms 83936 KB Output is correct
8 Correct 373 ms 83480 KB Output is correct
9 Correct 1980 ms 111132 KB Output is correct
10 Correct 1966 ms 111160 KB Output is correct
11 Correct 1974 ms 111180 KB Output is correct
12 Correct 2074 ms 111168 KB Output is correct
13 Correct 1004 ms 93120 KB Output is correct
14 Correct 558 ms 108132 KB Output is correct
15 Correct 2043 ms 111132 KB Output is correct
16 Correct 855 ms 103428 KB Output is correct
17 Correct 820 ms 103120 KB Output is correct
18 Correct 1171 ms 111488 KB Output is correct
19 Correct 918 ms 126392 KB Output is correct
20 Correct 942 ms 128032 KB Output is correct
21 Correct 864 ms 121368 KB Output is correct
22 Correct 849 ms 108228 KB Output is correct
23 Correct 760 ms 112160 KB Output is correct
24 Correct 944 ms 131552 KB Output is correct
25 Correct 938 ms 126100 KB Output is correct
26 Correct 917 ms 124276 KB Output is correct
27 Correct 738 ms 111148 KB Output is correct
28 Correct 820 ms 109840 KB Output is correct
29 Correct 2411 ms 123632 KB Output is correct
30 Correct 1575 ms 115700 KB Output is correct
31 Correct 2356 ms 117492 KB Output is correct
32 Correct 814 ms 107480 KB Output is correct
33 Correct 2398 ms 117468 KB Output is correct
34 Correct 833 ms 106848 KB Output is correct
35 Correct 2098 ms 117344 KB Output is correct
36 Correct 2383 ms 122852 KB Output is correct
37 Correct 1161 ms 124488 KB Output is correct
38 Correct 1452 ms 119752 KB Output is correct
39 Correct 835 ms 111288 KB Output is correct