답안 #289813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289813 2020-09-03T05:47:35 Z 최은수(#5769) 초대 (JOI12_invitation) C++17
20 / 100
3000 ms 72632 KB
#include<iostream>
#include<vector>
#include<queue>
#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=100010;
struct group
{
    int p,q,r,s,t;
    group(){}
    group(int p,int q,int r,int s,int t):p(p),q(q),r(r),s(s),t(t){}
};
struct event
{
    int h;
    int l,r;
    int cd;
    event(){}
    event(int h,int l,int r,int cd):h(h),l(l),r(r),cd(cd){}
    bool operator<(const event&x)const
    {
        return pair<int,pi>(-h,pi(cd,l))>pair<int,pi>(-x.h,pi(x.cd,x.l));
    }
};
vector<group>v;
bool chk[mx];
struct seg
{
    vector<int>t[mx*8];
    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].eb(p);
            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);
        return;
    }
    void query(int n,int s,int e,int x,vector<int>&v)
    {
        for(int&e:t[n])
            v.eb(e);
        t[n].clear();
        if(s==e)
            return;
        int m=s+(e-s)/2;
        if(x>m)
            query(n*2+1,m+1,e,x,v);
        else
            query(n*2,s,m,x,v);
        return;
    }
}stdog,stcat;
struct seg2
{
    int t[mx];
    void init(int n,int s,int e)
    {
        if(s==e)
        {
            t[n]=s;
            return;
        }
        int m=s+(e-s)/2;
        init(n*2,s,m);
        init(n*2+1,m+1,e);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
    void del(int n,int s,int e,int x)
    {
        if(s==e)
        {
            t[n]=inf;
            return;
        }
        int m=s+(e-s)/2;
        if(x>m)
            del(n*2+1,m+1,e,x);
        else
            del(n*2,s,m,x);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
    int query(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return inf;
        if(S<=s&&e<=E)
            return t[n];
        int m=s+(e-s)/2;
        return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
    }
}stmd,stmc;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c;
    cin>>a>>b>>c;
    int n;
    cin>>n;
    v.resize(n);
    for(auto&t:v)
        cin>>t.p>>t.q>>t.r>>t.s>>t.t;
    vector<int>cv1,cv2;
    for(auto&t:v)
        cv1.eb(t.p),cv1.eb(t.q+1),
        cv2.eb(t.r),cv2.eb(t.s+1);
    cv1.eb(c),cv1.eb(c+1);
    sort(all(cv1));
    cv1.erase(unique(all(cv1)),cv1.end());
    sort(all(cv2));
    cv2.erase(unique(all(cv2)),cv2.end());
    {
        if(cv1[0]!=1||cv2[0]!=1||cv1.back()!=a+1||cv2.back()!=b+1)
            return cout<<-1<<endl,0;
        vector<pi>v1,v2;
        for(auto&t:v)
            v1.eb(t.p,t.q),v2.eb(t.r,t.s);
        sort(all(v1)),sort(all(v2));
        int mx=0;
        for(pi&t:v1)
        {
            if(t.fi>mx+1)
                return cout<<-1<<endl,0;
            mx=max(mx,t.se);
        }
        mx=0;
        for(pi&t:v2)
        {
            if(t.fi>mx+1)
                return cout<<-1<<endl,0;
            mx=max(mx,t.se);
        }
    }
    int n1=(int)cv1.size()-1,n2=(int)cv2.size()-1;
    ll ans=0;
    v.eb(c,c,b,b,0);
    for(auto&t:v)
        t.p=lower_bound(all(cv1),t.p)-cv1.begin(),
        t.q=lower_bound(all(cv1),t.q+1)-cv1.begin()-1,
        t.r=lower_bound(all(cv2),t.r)-cv2.begin(),
        t.s=lower_bound(all(cv2),t.s+1)-cv2.begin()-1;
    for(int i=0;i<n;i++)
    {
        auto&t=v[i];
        stdog.upd(1,0,n1,t.p,t.q,i);
        stcat.upd(1,0,n2,t.r,t.s,i);
    }
    chk[n]=1;
    priority_queue<event>pq;
    pq.ep(0,v[n].p,v[n].q,0);
    stmd.init(1,0,n1);
    stmc.init(1,0,n2);
    while(!pq.empty())
    {
        event cur=pq.top();
        pq.pop();
        if(cur.cd==0)
        {
            int cid=stmd.query(1,0,n1,cur.l,cur.r);
            if(cid!=inf)
            {
                stmd.del(1,0,n1,cid);
                ans+=(ll)cur.h*(cv1[cid+1]-cv1[cid]);
                vector<int>getv;
                stdog.query(1,0,n1,cid,getv);
                for(int&t:getv)
                {
                    if(chk[t])
                        continue;
                    chk[t]=1;
                    pq.ep(v[t].t,v[t].p,v[t].q,0);
                    pq.ep(v[t].t,v[t].r,v[t].s,1);
                }
                cid=stmd.query(1,0,n1,cur.l,cur.r);
                if(cid!=inf)
                    pq.ep(cur);
            }
        }
        else
        {
            int cid=stmc.query(1,0,n2,cur.l,cur.r);
            if(cid!=inf)
            {
                stmc.del(1,0,n2,cid);
                ans+=(ll)cur.h*(cv2[cid+1]-cv2[cid]);
                vector<int>getv;
                stcat.query(1,0,n1,cid,getv);
                for(int&t:getv)
                {
                    if(chk[t])
                        continue;
                    chk[t]=1;
                    pq.ep(v[t].t,v[t].p,v[t].q,0);
                    pq.ep(v[t].t,v[t].r,v[t].s,1);
                }
                cid=stmc.query(1,0,n2,cur.l,cur.r);
                if(cid!=inf)
                    pq.ep(cur);
            }
        }
    }
    for(int i=0;i<n;i++)
        if(!chk[i])
            return cout<<-1<<endl,0;
    cout<<ans<<endl;
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 37888 KB Output is correct
2 Correct 26 ms 38016 KB Output is correct
3 Correct 27 ms 38012 KB Output is correct
4 Correct 26 ms 37888 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 38016 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 38392 KB Output is correct
2 Correct 29 ms 38204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 38776 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 38656 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3046 ms 69820 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3047 ms 72516 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3087 ms 69564 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3074 ms 66496 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 49100 KB Output is correct
2 Execution timed out 3079 ms 72632 KB Time limit exceeded
3 Halted 0 ms 0 KB -