oj.uz

Submission #347106

# Submission time Handle Problem Language Result Execution time Memory
347106 2021-01-11T20:01:38 Z YJU Two Dishes (JOI19_dishes) C++14
5 / 100
 766 ms 66272 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
ll n,m,a[N],s[N],p[N],b[N],t[N],q[N],ans,f[N];
vector<ll> ea[N],lis;
set<ll> ms;
 
int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,n)cin>>a[i]>>s[i]>>p[i],a[i]+=a[i-1];
	REP1(i,m)cin>>b[i]>>t[i]>>q[i],b[i]+=b[i-1];
	
	REP1(i,m){
		ea[lwb(a,a+n+1,t[i]-b[i]+1)-a+1].pb(i);
	}
	
	REP1(i,m)f[i]=(i==1?-INF:0)-q[i],ans+=q[i],ms.insert(i),lis.pb(i);
	
	REP1(i,n+1){
		
		for(auto j:ea[i])f[j]+=q[j],ans-=q[j],lis.pb(j),ms.insert(j);
		
		/*REP1(j,m){
			//cout<<f[j]<<(j==m?"\n":" ");
			if(f[j]<0){f[j+1]+=f[j];f[j]=0;}
		}*/
		
		//REP1(j,m)cout<<f[j]<<(j==m?"\n":" ");
		
		sort(lis.begin(),lis.end());
		//lis.resize(unique(lis.begin(),lis.end())-lis.begin());
		
		for(auto j:lis){
			auto l=ms.lwb(j),r=l;
			ll lst=0;
			while(r!=ms.end()){
				f[*r]+=lst;
				if(f[*r]>=0)break;
				lst=f[*r],f[*r++]=0;
			}
			ms.erase(l,r);
		}
		
		//REP1(j,m)cout<<f[j]<<(j==m?"\n":" ");
		lis.clear();
		//if(i==n+1)break;
		ll id=lwb(b+1,b+m+1,s[i]-a[i]+1)-b;
		if(s[i]-a[i]<b[0])id=1;
		f[1]+=p[i];f[id]-=p[i];
		lis.pb(1);lis.pb(id);
		ms.insert(1);ms.insert(id);
	}
	
	REP1(i,m)ans+=f[i];
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 63400 KB Output is correct
2 Correct 692 ms 63452 KB Output is correct
3 Correct 678 ms 61020 KB Output is correct
4 Correct 751 ms 66272 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 690 ms 61660 KB Output is correct
7 Correct 362 ms 49628 KB Output is correct
8 Correct 315 ms 35564 KB Output is correct
9 Correct 685 ms 61748 KB Output is correct
10 Correct 518 ms 59484 KB Output is correct
11 Correct 474 ms 55260 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Incorrect 16 ms 23916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Incorrect 16 ms 23916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Incorrect 16 ms 23916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Incorrect 16 ms 23916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Incorrect 16 ms 23916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 63400 KB Output is correct
2 Correct 692 ms 63452 KB Output is correct
3 Correct 678 ms 61020 KB Output is correct
4 Correct 751 ms 66272 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 690 ms 61660 KB Output is correct
7 Correct 362 ms 49628 KB Output is correct
8 Correct 315 ms 35564 KB Output is correct
9 Correct 685 ms 61748 KB Output is correct
10 Correct 518 ms 59484 KB Output is correct
11 Correct 474 ms 55260 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 16 ms 23916 KB Output is correct
14 Correct 17 ms 23916 KB Output is correct
15 Incorrect 16 ms 23916 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 63400 KB Output is correct
2 Correct 692 ms 63452 KB Output is correct
3 Correct 678 ms 61020 KB Output is correct
4 Correct 751 ms 66272 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 690 ms 61660 KB Output is correct
7 Correct 362 ms 49628 KB Output is correct
8 Correct 315 ms 35564 KB Output is correct
9 Correct 685 ms 61748 KB Output is correct
10 Correct 518 ms 59484 KB Output is correct
11 Correct 474 ms 55260 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 16 ms 23916 KB Output is correct
14 Correct 17 ms 23916 KB Output is correct
15 Incorrect 16 ms 23916 KB Output isn't correct
16 Halted 0 ms 0 KB -