#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].a-1);
v.pb(dog[i].b+1);
v.pb(cat[i].a);
v.pb(cat[i].a-1);
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);
}
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);
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |