oj.uz

Submission #283739

# Submission time Handle Problem Language Result Execution time Memory
283739 2020-08-26T06:34:14 Z 최은수(#5746) 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 2062 ms 133300 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct dsu
{
    int pa[mx];
    int par(int x)
    {
        if(pa[x]==0)
            return x;
        return pa[x]=par(pa[x]);
    }
    inline void uni(int x,int y)
    {
        x=par(x);
        y=par(y);
        if(x==y)
            return;
        pa[x]=y;
        return;
    }
}uf;
struct seg
{
    int t[2400010];
    bool t2[2400010];
    void init(int n,int s,int e)
    {
        t[n]=0;
        t2[n]=0;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        init(n*2,s,m);
        init(n*2+1,m+1,e);
        return;
    }
    void upd(int n,int s,int e,int S,int E,int p)
    {
        if(s>E||S>e)
            return;
        if(S<=s&&e<=E)
        {
            t[n]+=p;
            t2[n]=t[n]>0?1:(s==e?0:t2[n*2]||t2[n*2+1]);
            return;
        }
        int m=s+(e-s)/2;
        upd(n*2,s,m,S,E,p);
        upd(n*2+1,m+1,e,S,E,p);
        t2[n]=t[n]>0?1:t2[n*2]||t2[n*2+1];
        return;
    }
    bool query(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return 0;
        if(t[n]>0)
            return 1;
        if(S<=s&&e<=E)
            return t2[n];
        int m=s+(e-s)/2;
        return query(n*2,s,m,S,E)||query(n*2+1,m+1,e,S,E);
    }
}st;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,c;
    cin>>n>>m>>c;
    vector<pi>v(n);
    vector<pair<pi,pi> >mv(m);
    vector<int>cxv,cyv;
    for(pi&t:v)
        cin>>t.fi>>t.se,cxv.eb(t.fi),cyv.eb(t.se);
    for(auto&t:mv)
        cin>>t.fi.fi>>t.se.fi>>t.fi.se>>t.se.se,
        cxv.eb(t.fi.fi),cxv.eb(t.fi.se),cyv.eb(t.se.fi),cyv.eb(t.se.se);
    sort(all(cxv));
    sort(all(cyv));
    cxv.erase(unique(all(cxv)),cxv.end());
    cyv.erase(unique(all(cyv)),cyv.end());
    for(pi&t:v)
        t.fi=upper_bound(all(cxv),t.fi)-cxv.begin(),
        t.se=upper_bound(all(cyv),t.se)-cyv.begin();
    v.insert(v.begin(),v[0]);
    for(auto&t:mv)
        t.fi.fi=upper_bound(all(cxv),t.fi.fi)-cxv.begin(),
        t.fi.se=upper_bound(all(cxv),t.fi.se)-cxv.begin(),
        t.se.fi=upper_bound(all(cyv),t.se.fi)-cyv.begin(),
        t.se.se=upper_bound(all(cyv),t.se.se)-cyv.begin();
    int xn=cxv.size(),yn=cyv.size();
    vector<int>sv;
    for(int i=0;i++<n;)
        sv.eb(i);
    vector<vector<pi> >xsv(xn+1);
    vector<vector<pi> >ysv(yn+1);
    sort(all(sv),[&](const int&x,const int&y){return v[x]<v[y];});
    for(int i=1;i<n;i++)
        if(v[sv[i]].fi==v[sv[i-1]].fi)
            xsv[v[sv[i]].fi].eb(sv[i-1],sv[i]);
    sort(all(sv),[&](const int&x,const int&y){return pi(v[x].se,v[x].fi)<pi(v[y].se,v[y].fi);});
    for(int i=1;i<n;i++)
        if(v[sv[i]].se==v[sv[i-1]].se)
            ysv[v[sv[i]].se].eb(sv[i-1],sv[i]);
    vector<vector<pi> >xqv(xn+1),xdv(xn+1);
    vector<vector<pi> >yqv(yn+1),ydv(yn+1);
    for(auto&t:mv)
        xqv[t.fi.fi].eb(t.se),xdv[t.fi.se].eb(t.se),
        yqv[t.se.fi].eb(t.fi),ydv[t.se.se].eb(t.fi);
    vector<pair<int,pi> >ev;
    st.init(1,1,yn);
    for(int i=0;i++<xn;)
    {
        for(pi&t:xqv[i])
            st.upd(1,1,yn,t.fi,t.se,1);
        for(pi&t:xsv[i])
            if(!st.query(1,1,yn,v[t.fi].se,v[t.se].se))
                ev.eb(cyv[v[t.se].se-1]-cyv[v[t.fi].se-1],t);
        for(pi&t:xdv[i])
            st.upd(1,1,yn,t.fi,t.se,-1);
    }
    st.init(1,1,xn);
    for(int i=0;i++<yn;)
    {
        for(pi&t:yqv[i])
            st.upd(1,1,xn,t.fi,t.se,1);
        for(pi&t:ysv[i])
            if(!st.query(1,1,xn,v[t.fi].fi,v[t.se].fi))
                ev.eb(cxv[v[t.se].fi-1]-cxv[v[t.fi].fi-1],t);
        for(pi&t:ydv[i])
            st.upd(1,1,xn,t.fi,t.se,-1);
    }
    vector<int>wv;
    sort(all(ev));
    for(auto&t:ev)
    {
        if(uf.par(t.se.fi)!=uf.par(t.se.se))
            wv.eb(t.fi);
        uf.uni(t.se.fi,t.se.se);
    }
    vector<ll>ps(1,0);
    for(int&t:wv)
        ps.eb(ps.back()+t);
    for(int i=0;i<c;i++)
    {
        int b,h;
        cin>>b>>h;
        if((int)wv.size()+h<n)
        {
            cout<<-1<<'\n';
            continue;
        }
        int pos=max(n-h,(int)(lower_bound(all(wv),b)-wv.begin()));
        cout<<(ps[pos]+(ll)(n-pos)*b)<<'\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3704 KB Output is correct
2 Correct 322 ms 29000 KB Output is correct
3 Correct 346 ms 28424 KB Output is correct
4 Correct 351 ms 19636 KB Output is correct
5 Correct 369 ms 31020 KB Output is correct
6 Correct 354 ms 28516 KB Output is correct
7 Correct 203 ms 18520 KB Output is correct
8 Correct 237 ms 31404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3704 KB Output is correct
2 Correct 322 ms 29000 KB Output is correct
3 Correct 346 ms 28424 KB Output is correct
4 Correct 351 ms 19636 KB Output is correct
5 Correct 369 ms 31020 KB Output is correct
6 Correct 354 ms 28516 KB Output is correct
7 Correct 203 ms 18520 KB Output is correct
8 Correct 237 ms 31404 KB Output is correct
9 Correct 2062 ms 116212 KB Output is correct
10 Correct 1835 ms 117860 KB Output is correct
11 Correct 1885 ms 119424 KB Output is correct
12 Correct 1786 ms 119476 KB Output is correct
13 Correct 763 ms 31388 KB Output is correct
14 Correct 365 ms 32708 KB Output is correct
15 Correct 1808 ms 118568 KB Output is correct
16 Correct 514 ms 37596 KB Output is correct
17 Correct 545 ms 37564 KB Output is correct
18 Correct 874 ms 88484 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3704 KB Output is correct
2 Correct 322 ms 29000 KB Output is correct
3 Correct 346 ms 28424 KB Output is correct
4 Correct 351 ms 19636 KB Output is correct
5 Correct 369 ms 31020 KB Output is correct
6 Correct 354 ms 28516 KB Output is correct
7 Correct 203 ms 18520 KB Output is correct
8 Correct 237 ms 31404 KB Output is correct
9 Correct 624 ms 39584 KB Output is correct
10 Correct 555 ms 38776 KB Output is correct
11 Correct 544 ms 37256 KB Output is correct
12 Correct 512 ms 27832 KB Output is correct
13 Correct 458 ms 40004 KB Output is correct
14 Correct 586 ms 43980 KB Output is correct
15 Correct 567 ms 39620 KB Output is correct
16 Correct 562 ms 38980 KB Output is correct
17 Correct 381 ms 27612 KB Output is correct
18 Correct 471 ms 40516 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3704 KB Output is correct
2 Correct 322 ms 29000 KB Output is correct
3 Correct 346 ms 28424 KB Output is correct
4 Correct 351 ms 19636 KB Output is correct
5 Correct 369 ms 31020 KB Output is correct
6 Correct 354 ms 28516 KB Output is correct
7 Correct 203 ms 18520 KB Output is correct
8 Correct 237 ms 31404 KB Output is correct
9 Correct 2062 ms 116212 KB Output is correct
10 Correct 1835 ms 117860 KB Output is correct
11 Correct 1885 ms 119424 KB Output is correct
12 Correct 1786 ms 119476 KB Output is correct
13 Correct 763 ms 31388 KB Output is correct
14 Correct 365 ms 32708 KB Output is correct
15 Correct 1808 ms 118568 KB Output is correct
16 Correct 514 ms 37596 KB Output is correct
17 Correct 545 ms 37564 KB Output is correct
18 Correct 874 ms 88484 KB Output is correct
19 Correct 624 ms 39584 KB Output is correct
20 Correct 555 ms 38776 KB Output is correct
21 Correct 544 ms 37256 KB Output is correct
22 Correct 512 ms 27832 KB Output is correct
23 Correct 458 ms 40004 KB Output is correct
24 Correct 586 ms 43980 KB Output is correct
25 Correct 567 ms 39620 KB Output is correct
26 Correct 562 ms 38980 KB Output is correct
27 Correct 381 ms 27612 KB Output is correct
28 Correct 471 ms 40516 KB Output is correct
29 Correct 1995 ms 123316 KB Output is correct
30 Correct 1088 ms 75764 KB Output is correct
31 Correct 1895 ms 117272 KB Output is correct
32 Correct 471 ms 31220 KB Output is correct
33 Correct 1896 ms 117076 KB Output is correct
34 Correct 509 ms 33476 KB Output is correct
35 Correct 1860 ms 133300 KB Output is correct
36 Correct 1951 ms 122424 KB Output is correct
37 Correct 672 ms 40128 KB Output is correct
38 Correct 992 ms 88836 KB Output is correct
39 Correct 484 ms 38088 KB Output is correct