oj.uz

Submission #851114

# Submission time Handle Problem Language Result Execution time Memory
851114 2023-09-18T14:17:55 Z CSQ31 Distributing Candies (IOI21_candies) C++17
100 / 100
 2305 ms 90332 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];
int n,q;
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 -1e18;
	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+1,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;
ll cursum = 0;
void solve(int v,int tl,int tr){
	for(auto x:ch[v]){
		upd(1,x.fi,q,0,q,x.se);
		cursum+=x.se;
	}
	if(tl==tr){
		int l = 0,r = q;
		//cout<<tl<<" "<<mnn[1]<<" "<<mxx[1]<<'\n';
		while(r>=l){
			int mid = (l+r)/2;
			ll rmn = mnquery(1,mid,q,0,q);
			ll rmx = mxquery(1,mid,q,0,q);
			if(rmx - rmn< C[tl])r = mid-1;
			else l = mid+1;
		}
		if(r==-1)ans[tl] = cursum - mnn[1];
		else{
			ll a = mnquery(1,r,q,0,q);
			ll b = mxquery(1,r,q,0,q);
			if(mnquery(1,r,r,0,q) == a)ans[tl] = C[tl] - (b - cursum);
			else ans[tl] = cursum - a;
		}
		for(auto x:ch[v]){
			upd(1,x.fi,q,0,q,-x.se);
			cursum-=x.se;
		}
		
		return;
	}
	int tm = (tl+tr)/2;
	solve(2*v,tl,tm);
	solve(2*v+1,tm+1,tr);
	for(auto x:ch[v]){
		upd(1,x.fi,q,0,q,-x.se);
		cursum-=x.se;
	}
}
vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v){
    n = sz(c);
    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 5 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 7 ms 27408 KB Output is correct
4 Correct 8 ms 27224 KB Output is correct
5 Correct 13 ms 27484 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2162 ms 83196 KB Output is correct
2 Correct 2305 ms 85908 KB Output is correct
3 Correct 2260 ms 87180 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 704 ms 63536 KB Output is correct
3 Correct 344 ms 26536 KB Output is correct
4 Correct 2221 ms 83368 KB Output is correct
5 Correct 2144 ms 90332 KB Output is correct
6 Correct 2081 ms 90012 KB Output is correct
7 Correct 2060 ms 89432 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27224 KB Output is correct
3 Correct 111 ms 44768 KB Output is correct
4 Correct 288 ms 29760 KB Output is correct
5 Correct 840 ms 48116 KB Output is correct
6 Correct 848 ms 48148 KB Output is correct
7 Correct 790 ms 48092 KB Output is correct
8 Correct 835 ms 48024 KB Output is correct
9 Correct 931 ms 48240 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 7 ms 27408 KB Output is correct
4 Correct 8 ms 27224 KB Output is correct
5 Correct 13 ms 27484 KB Output is correct
6 Correct 2162 ms 83196 KB Output is correct
7 Correct 2305 ms 85908 KB Output is correct
8 Correct 2260 ms 87180 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 704 ms 63536 KB Output is correct
11 Correct 344 ms 26536 KB Output is correct
12 Correct 2221 ms 83368 KB Output is correct
13 Correct 2144 ms 90332 KB Output is correct
14 Correct 2081 ms 90012 KB Output is correct
15 Correct 2060 ms 89432 KB Output is correct
16 Correct 5 ms 27224 KB Output is correct
17 Correct 5 ms 27224 KB Output is correct
18 Correct 111 ms 44768 KB Output is correct
19 Correct 288 ms 29760 KB Output is correct
20 Correct 840 ms 48116 KB Output is correct
21 Correct 848 ms 48148 KB Output is correct
22 Correct 790 ms 48092 KB Output is correct
23 Correct 835 ms 48024 KB Output is correct
24 Correct 931 ms 48240 KB Output is correct
25 Correct 6 ms 27228 KB Output is correct
26 Correct 297 ms 26628 KB Output is correct
27 Correct 709 ms 64976 KB Output is correct
28 Correct 2216 ms 86424 KB Output is correct
29 Correct 2239 ms 88112 KB Output is correct
30 Correct 2259 ms 88440 KB Output is correct
31 Correct 2298 ms 88792 KB Output is correct
32 Correct 2176 ms 87636 KB Output is correct