Submission #1128442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128442		modwwe	초대 (JOI12_invitation)	C++20	100 / 100	911 ms	107000 KiB

invitation

#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
void phongbeo();
const int inf = 2e9;
const ll mod2 = 1e9+7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,ans ;
int kk;
int el = 19;
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    //modwwe
    phongbeo(),down
    // checktime
}
vector<int> ask[2400001],v;
ib dog[100001], cat[100001];
int money[100001];
///bool vis[2400001];
int f[600001];
int cost[600001];
bool vis[600001];
bool d[100001];
int a,b,c;
struct segtree
{
    ib t[2400001];
    int t2[2400001];
    int minn[2400001];
    void apply(int node,int x)
    {
        t2[node]=max(t2[node],x);
        t[node]=mer({x,minn[node]},t[node]);
    }
    ib mer(ib x,ib y)
    {
        if(cost[x.b]==0) return y;
        if(cost[y.b]==0) return x;
        if(x.a>=y.a) return x;
        return y;
    }
    int mer2(int x,int y)
    {
        if(cost[x]==0) return y;
        return x;
    }
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            apply(i,t2[x]);
        t2[x]=0;
    }
    void setup(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            ask[node].pb(x);
            return;
        }
        int mid=l+r>>1;
        setup(node<<1,l,mid,l1,r1,x);
        setup(node<<1|1,mid+1,r,l1,r1,x);
    }
    void build(int node,int l,int r)
    {
        if(l==r)
        {
            t[node]= {-1,l};
            cost[l]=v[l]-v[l-1];
            minn[node]= l;
            f[l]=node;
            return;
        }
        int mid=l+r>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        t[node]=mer(t[node<<1],t[node<<1|1]);
        minn[node]=mer2(minn[node<<1],minn[node<<1|1]);
    }
    void eat(int node,int l,int r,int l1,int x)
    {
        if(l==r)
        {
            if(x==1)
            {
                s4+=t[node].a;
                cost[l]--;
                s5++;
            }
            else s4+=1ll*cost[l]*t[node].a,s5+=cost[l],cost[l]=0;
            return;
        }
        int mid=l+r>>1;
        if(t2[node]!=0)ff(node);
        if(l1<=mid) eat(node<<1,l,mid,l1,x);
        else eat(node<<1|1,mid+1,r,l1,x);
        t[node]=mer(t[node<<1],t[node<<1|1]);
        minn[node]=mer2(minn[node<<1],minn[node<<1|1]);
    }
    void upd(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            apply(node,x);
            return;
        }
        if(t2[node]!=0)ff(node);
        int mid=l+r>>1;
        upd(node<<1,l,mid,l1,r1,x);
        upd(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=mer(t[node<<1],t[node<<1|1]);
    }
} st;
int cl(int x)
{
    x=lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    return x;
}
void upd2(int x)
{
    if(d[x])return;
    d[x]=1;
    st.upd(1,1,n,dog[x].a,dog[x].b,money[x]);
    st.upd(1,1,n,cat[x].a,cat[x].b,money[x]);
}
void upd(int x)
{
    st.eat(1,1,n,x,1);
    x=f[x];
    while(x!=0)
    {
        for(auto f:ask[x])
            upd2(f);
        vector<int>().swap(ask[x]);
        x=(x>>1);
    }
}
void phongbeo()
{
    cin>>a>>b>>c;
    n=a+b;
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>dog[i].a>>dog[i].b;
        cin>>cat[i].a>>cat[i].b;
        cin>>money[i];
        cat[i].a+=a;
        cat[i].b+=a;
        v.pb(dog[i].a);
        v.pb(dog[i].b+1);
        v.pb(cat[i].a);
        v.pb(cat[i].b+1);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    n=v.size()-1;
    for(int i=1; i<=m; i++)
    {
        dog[i]= {cl(dog[i].a),cl(dog[i].b+1)-1};
        cat[i]= {cl(cat[i].a),cl(cat[i].b+1)-1};
        st.setup(1,1,n,dog[i].a,dog[i].b,i);
        st.setup(1,1,n,cat[i].a,cat[i].b,i);
    }
    st.build(1,1,n);
    int kk=upper_bound(v.begin(),v.end(),c)-v.begin();
    vector<int>().swap(v);
    if(kk==0)
    {
        cout<<-1;
    }
    upd(kk);
    s4=0;
    while(true)
    {
        ib x=st.t[1];

        if(cost[x.b]==0||x.a==-1)break;
        if(vis[x.b]==0)upd(x.b);
        else st.eat(1,1,n,x.b,-1);
        vis[x.b]=1;
    }
    if(s5!=a+b)cout<<-1;
    else cout<<s4;
}

Compilation message (stderr)

invitation.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main()
      | ^~~~
invitation.cpp: In function 'int main()':
invitation.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
invitation.cpp:78:9: note: in expansion of macro 'fin'
   78 |         fin(task2);
      |         ^~~
invitation.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
invitation.cpp:79:9: note: in expansion of macro 'fou'
   79 |         fou(task2);
      |         ^~~
invitation.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
invitation.cpp:83:9: note: in expansion of macro 'fin'
   83 |         fin(task);
      |         ^~~
invitation.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
invitation.cpp:84:9: note: in expansion of macro 'fou'
   84 |         fou(task);
      |         ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10