Submission #1190783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190783		vnedu	도로 건설 사업 (JOI13_construction)	C++17	0 / 100	8 ms	1404 KiB

construction

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int MAXVAL=N*6;
struct segtree
{
    int t[MAXVAL<<2],laz[MAXVAL<<2];
    segtree() {}
    void push(int id)
    {
        if(!laz[id]) return;
        t[id<<1]+=laz[id],laz[id<<1]+=laz[id];
        t[id<<1|1]+=laz[id],laz[id<<1|1]+=laz[id];
        laz[id]=0;
    }
    void add(int id, int l, int r, int u, int v, int val)
    {
        if(l>v||r<u) return;
        if(u<=l && r<=v)
        {
            t[id]+=val;
            laz[id]+=val;
            return;
        }
        int mid=(l+r)>>1;
        push(id);
        add(id<<1,l,mid,u,v,val);
        add(id<<1|1,mid+1,r,u,v,val);
        t[id]=max(t[id<<1],t[id<<1|1]);
    }
    int get(int id, int l, int r, int u, int v)
    {
        if(l>v || r<u) return INT_MIN;
        if(u<=l && r<=v) return t[id];
        push(id);
        int mid=(l+r)>>1;
        return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
    }
} stree;
struct Point
{
    int x,y;
    Point() {}
    Point(int x, int y) : x(x),y(y) {}
} point[N];
struct Rec
{
    int b,t,l,r;
    Rec() {}
    Rec(int b, int t, int l, int r) :b(b),t(t),l(l),r(r) {}
} rec[M];
struct Edge
{
    int u,v,w;
    bool useful;
    Edge() {}
    Edge(int u, int v, int w) : u(u),v(v),w(w) {}
    bool operator < (const Edge &S) const
    {
        return w<S.w;
    }
} edge[2*N];
struct Query
{
    int x,l,r,val,id;
    bool isQuery;
    Query() {}
    Query(int x, int l, int r, int val, int id, bool isQuery) : x(x),l(l),r(r),val(val),id(id),isQuery(isQuery) {}
    bool operator < (const Query &S) const
    {
        if(x!=S.x) return x<S.x;
        return isQuery<S.isQuery;
    }
};
struct Dsu
{
    int par[N],n;
    Dsu() {}
    void init(int _n)
    {
        n=_n;
        for(int i=1;i<=n;++i) par[i]=i;
    }
    int get(int x)
    {
        if(x==par[x]) return x;
        return par[x]=get(par[x]);
    }
    bool unite(int x, int y)
    {
        int s=get(x),t=get(y);
        if(s==t) return 0;
        par[s]=t;
        return 1;
    }
} dsu;
int n,m,c,numEdge=0,cord[N],a[2*N],ptr=0;
ll p[2*N];
vector<int> nen;
vector<Query> query;
bool cmp1(int id1, int id2)
{
    Point &x=point[id1];
    Point &y=point[id2];
    if(x.x!=y.x) return x.x<y.x;
    return x.y<y.y;
}
bool cmp2(int id1, int id2)
{
    Point &x=point[id1];
    Point &y=point[id2];
    if(x.y!=y.y) return x.y<y.y;
    return x.x<y.x;
}
void solve()
{
    cin>>n>>m>>c;
    for(int i=1;i<=n;++i)
    {
        cord[i]=i;
        int x,y; cin>>x>>y;
        nen.pb(x);
        nen.pb(y);
        point[i]=Point(x,y);
    }
    for(int i=1;i<=m;++i)
    {
        int b,t,l,r;
        cin>>l>>b>>r>>t;
        nen.pb(b);
        nen.pb(t);
        nen.pb(l);
        nen.pb(r);
        rec[i]=Rec(b,t,l,r);
    }
    sort(all(nen));
    nen.erase(unique(all(nen)),nen.end());

    // case vertical
    sort(cord+1,cord+1+n,cmp1);
    for(int i=1;i<=n;)
    {
        int val=point[cord[i]].x,lst=-1;
        while(i<=n && point[cord[i]].x==val)
        {
            if(lst!=-1)
            {
                edge[++numEdge]=Edge(lst,cord[i],point[cord[i]].y-point[lst].y);
                query.pb(Query(val,point[lst].y,point[cord[i]].y,-324876,numEdge,1));
            }
            lst=cord[i];
            ++i;
        }
    }
    for(int i=1;i<=m;++i)
    {
        int b=rec[i].b;
        int t=rec[i].t;
        int l=rec[i].l;
        int r=rec[i].r;
        query.pb(Query(l,b,t,1,-1,0));
        query.pb(Query(r+1,b,t,-1,-1,0));
    }
    sort(all(query));
    for(Query &cm : query)
    {
        if(cm.isQuery==0)
        {
            stree.add(1,1,(int)nen.size(),cm.l,cm.r,cm.val);
        }
        else
        {
            int val=stree.get(1,1,(int)nen.size(),cm.l,cm.r);
            edge[cm.id].useful=(val==0);
        }
    }

    // case horizontal
    query.clear();
    sort(cord+1,cord+1+n,cmp2);
    for(int i=1;i<=n;)
    {
        int val=point[cord[i]].y,lst=-1;
        while(i<=n && point[cord[i]].y==val)
        {
            if(lst!=-1)
            {
                edge[++numEdge]=Edge(lst,cord[i],point[cord[i]].x-point[lst].x);
                query.pb(Query(val,point[lst].x,point[cord[i]].x,-4243423,numEdge,1));
            }
            lst=cord[i];
            ++i;
        }
    }
    for(int i=1;i<=m;++i)
    {
        int b=rec[i].b;
        int t=rec[i].t;
        int l=rec[i].l;
        int r=rec[i].r;
        query.pb(Query(b,l,r,1,-123321,0));
        query.pb(Query(t+1,l,r,-1,-123321,0));
    }
    sort(all(query));
    for(Query &cm : query)
    {
        if(cm.isQuery==0)
        {
            stree.add(1,1,(int)nen.size(),cm.l,cm.r,cm.val);
        }
        else
        {
            int val=stree.get(1,1,(int)nen.size(),cm.l,cm.r);
//            cout<<edge[cm.id].u<<' '<<edge[cm.id].v<<' '<<val<<'\n';
            edge[cm.id].useful=(val==0);
        }
    }
//    return;
    // end case
    dsu.init(n);
    sort(edge+1,edge+1+numEdge);
    ll sum=0;
    int numComp=n;
//    for(int i=1;i<=numEdge;++i) if(edge[i].useful)
//    {
//        cout<<edge[i].u<<' '<<edge[i].v<<' '<<edge[i].w<<'\n';
//    }
//    return;
    for(int i=1;i<=numEdge;++i) if(edge[i].useful && dsu.unite(edge[i].u,edge[i].v)) a[++ptr]=edge[i].w,sum+=edge[i].w,--numComp;
    sort(a+1,a+1+ptr);
    for(int i=ptr;i>=1;--i) p[i]=a[i]+p[i+1];
//    cout<<numComp<<' '<<sum<<'\n';
//    return;
    while(c--)
    {
        int b,h; cin>>b>>h;
        h-=numComp;
        if(h<0)
        {
            cout<<-1<<'\n';
            continue;
        }
        ll ans=sum+numComp*1LL*b;
        int pos=lower_bound(a+1,a+1+ptr,b)-a;
        maximize(pos,ptr-h+1);
        ans+=b*1LL*(ptr-pos+1)-p[pos];
        cout<<ans<<'\n';
//        cout<<"DSA\n";
//        cout<<ptr-pos+1<<'\n';
//        cout<<"DSA\n";
    }
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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