oj.uz

Submission #851113

# Submission time Handle Problem Language Result Execution time Memory
851113 2023-09-18T14:15:12 Z CSQ31 Distributing Candies (IOI21_candies) C++17
29 / 100
 2133 ms 83344 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];
			return;
		}
		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
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2133 ms 83344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 106 ms 44592 KB Output is correct
4 Correct 300 ms 29760 KB Output is correct
5 Correct 855 ms 48084 KB Output is correct
6 Correct 815 ms 52672 KB Output is correct
7 Correct 798 ms 52772 KB Output is correct
8 Correct 840 ms 51716 KB Output is correct
9 Correct 934 ms 53360 KB Output is correct

Subtask #5
0 / 33.0

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