oj.uz

Submission #851094

# Submission time Handle Problem Language Result Execution time Memory
851094 2023-09-18T13:55:35 Z CSQ31 Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 72064 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
const int MAXN = 2e5+5;
ll mnn[4*MAXN],mxx[4*MAXN],lazy[4*MAXN],ans[MAXN],C[MAXN];
void upd(int v,int l,int r,int tl,int tr,ll val){
	if(l==tl && r==tr){
		lazy[v]+=val;
		mnn[v]+=val;
		mxx[v]+=val;
		return;
	}
	int tm = (tl+tr)/2;
	if(r<=tm)upd(2*v,l,r,tl,tm,val);
	else if(l>tm)upd(2*v+1,l,r,tm+1,tr,val);
	else{
		upd(2*v,l,tm,tl,tm,val);
		upd(2*v+1,tm+1,r,tm+1,tr,val);
	}
	
	mnn[v] = min(mnn[2*v],mnn[2*v+1])+lazy[v];
	mxx[v] = max(mxx[2*v],mxx[2*v+1])+lazy[v];
}
ll mnquery(int v,int l,int r,int tl,int tr){
	if(l>r)return 1e18;
	if(l==tl && r==tr)return mnn[v];
	int tm = (tl+tr)/2;
	return min(mnquery(2*v,l,min(r,tm),tl,tm),
	           mnquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v];
}
ll mxquery(int v,int l,int r,int tl,int tr){
	if(l>r)return 0;
	if(l==tl && r==tr)return mxx[v];
	int tm = (tl+tr)/2;
	return max(mxquery(2*v,l,min(r,tm),tl,tm),
	           mxquery(2*v+1,max(tm+1,l),r,tm+1,tr)) + lazy[v];
}

vector<pair<int,int>>ch[4*MAXN];
void add(int v,int l,int r,int tl,int tr,int t,ll val){
	if(l>r)return;
	if(l==tl && r==tr){
		ch[v].pb({t,val});
		return;
	}
	int tm = (tl+tr)/2;
	add(2*v,l,min(r,tm),tl,tm,t,val);
	add(2*v+1,max(tm+1,l),r,tm+1,tr,t,val);
}
set<pair<int,int>>cur;
void solve(int v,int tl,int tr){
	for(auto x:ch[v])cur.insert(x);
	if(tl==tr){
		vector<ll>p = {0};
		ans[tl] = 0;
		for(auto x:cur){
			ans[tl]+=x.se;
			ans[tl] = max(ans[tl],0LL);
			ans[tl] = min(ans[tl],C[tl]);
		}
		/*
		ll mn = 1e18;
		ll mx = -1e18;
		for(int i=sz(p)-1;i>=0;i--){
			mn = min(mn,p[i]);
			mx = max(mx,p[i]);
			if(mx-mn >= C[tl]){
				if(p[i]==mn)ans[tl] = C[tl] - (mx - p.back());
				else ans[tl] = p.back() - mn;
				break;
			}
			
		}
		if(mx-mn < C[tl])ans[tl] = p.back()-mn;
		* */
		for(auto x:ch[v])cur.erase(x);
		return;
	}
	int tm = (tl+tr)/2;
	solve(2*v,tl,tm);
	solve(2*v+1,tm+1,tr);
	for(auto x:ch[v])cur.erase(x);
}
vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){
    int n = sz(c);
    int q = sz(l);
    
    for(int i=0;i<n;i++)C[i] = c[i];
    for(int i=0;i<q;i++)add(1,l[i],r[i],0,n-1,i,v[i]);
    solve(1,0,n-1);
    vector<int>tmp(n);
    for(int i=0;i<n;i++)tmp[i] = ans[i];
    return tmp;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 7 ms 21148 KB Output is correct
4 Correct 7 ms 21336 KB Output is correct
5 Correct 15 ms 21340 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5016 ms 65900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Correct 1890 ms 51756 KB Output is correct
3 Correct 559 ms 29424 KB Output is correct
4 Execution timed out 5103 ms 72064 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 2074 ms 36784 KB Output is correct
4 Correct 1502 ms 25668 KB Output is correct
5 Execution timed out 5073 ms 38340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 4 ms 21084 KB Output is correct
3 Correct 7 ms 21148 KB Output is correct
4 Correct 7 ms 21336 KB Output is correct
5 Correct 15 ms 21340 KB Output is correct
6 Execution timed out 5016 ms 65900 KB Time limit exceeded
7 Halted 0 ms 0 KB -