oj.uz

Submission #754441

# Submission time Handle Problem Language Result Execution time Memory
754441 2023-06-07T19:01:46 Z tolbi Distributing Candies (IOI21_candies) C++17
67 / 100
 886 ms 48404 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (int i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define int long long
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "candies.h"
struct LSegTree{
	vector<int> segtree;
	vector<int> lazy;
	LSegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
		lazy.resize(segtree.size(), 0ll);
	}
	void dallan(int node, int sz){
		segtree[node]+=sz*lazy[node];
		if (sz!=1){
			lazy[node*2+1]+=lazy[node];
			lazy[node*2+2]+=lazy[node];
		}
		lazy[node]=0ll;
	}
	void update(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node,r-l+1);
		if (l>=tarl && r<=tarr){
			lazy[node]+=val;
			dallan(node,r-l+1);
			return;
		}
		if (l>tarr || r<tarl) return;
		int mid = l+(r-l)/2;
		update(tarl, tarr, val, l, mid, node*2+1);
		update(tarl, tarr, val, mid+1, r, node*2+2);
		segtree[node]=segtree[node*2+1]+segtree[node*2+2];
	}
	int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node,r-l+1);
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return 0ll;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return lnode+rnode;
	}
};//Normal Segment Tree
template<typename T> struct SegTreeBeats{
struct Node{
	T sum, lazy, max1, max2, min1, min2, maxc, minc;
	Node():sum(0),lazy(0),max1(0),min1(0),max2(-INF),min2(INF),minc(1),maxc(1){}
};
vector<Node> segtree;
void merge(int node){
	segtree[node].sum=segtree[node*2+1].sum+segtree[node*2+2].sum;
	if (segtree[node*2+1].max1==segtree[node*2+2].max1){
		segtree[node].max1=segtree[node*2+1].max1;
		segtree[node].maxc=segtree[node*2+1].maxc+segtree[node*2+2].maxc;
		segtree[node].max2=max(segtree[node*2+1].max2,segtree[node*2+2].max2);
	}
	else if (segtree[node*2+1].max1>segtree[node*2+2].max1){
		segtree[node].max1=segtree[node*2+1].max1;
		segtree[node].maxc=segtree[node*2+1].maxc;
		segtree[node].max2=max(segtree[node*2+1].max2,segtree[node*2+2].max1);
	}
	else {
		segtree[node].max1=segtree[node*2+2].max1;
		segtree[node].maxc=segtree[node*2+2].maxc;
		segtree[node].max2=max(segtree[node*2+2].max2,segtree[node*2+1].max1);
	}
	if (segtree[node*2+1].min1==segtree[node*2+2].min1){
		segtree[node].min1=segtree[node*2+1].min1;
		segtree[node].minc=segtree[node*2+1].minc+segtree[node*2+2].minc;
		segtree[node].min2=min(segtree[node*2+1].min2,segtree[node*2+2].min2);
	}
	else if (segtree[node*2+1].min1<segtree[node*2+2].min1){
		segtree[node].min1=segtree[node*2+1].min1;
		segtree[node].minc=segtree[node*2+1].minc;
		segtree[node].min2=min(segtree[node*2+1].min2,segtree[node*2+2].min1);
	}
	else {
		segtree[node].min1=segtree[node*2+2].min1;
		segtree[node].minc=segtree[node*2+2].minc;
		segtree[node].min2=min(segtree[node*2+2].min2,segtree[node*2+1].min1);
	}
}
void upd_lazy(int node, int val, int sz){
	segtree[node].sum+=val*sz;
	segtree[node].max1+=val;
	segtree[node].min1+=val;
	segtree[node].lazy+=val;
	if (segtree[node].max2!=-INF) segtree[node].max2+=val;
	if (segtree[node].min2!=INF) segtree[node].min2+=val;
}
void upd_chmin(int node, int val, int sz){
	if (val>=segtree[node].max1) return;
	segtree[node].sum-=segtree[node].max1*segtree[node].maxc;
	segtree[node].max1=val;
	segtree[node].sum+=segtree[node].max1*segtree[node].maxc;
	if (sz==1){
		segtree[node].min1=segtree[node].max1;
	}
	else {
		if (val<=segtree[node].min1) segtree[node].min1=val;
		else if (val<=segtree[node].min2) segtree[node].min2=val;
	}
}
void upd_chmax(int node, int val, int sz){
	if (val<=segtree[node].min1) return;
	segtree[node].sum-=segtree[node].min1*segtree[node].minc;
	segtree[node].min1=val;
	segtree[node].sum+=segtree[node].min1*segtree[node].minc;
	if (sz==1){
		segtree[node].max1=segtree[node].min1;
	}
	else {
		if (val>=segtree[node].max1) segtree[node].max1=val;
		else if (val>=segtree[node].max2) segtree[node].max2=val;
	}
}
void dallan(int node, int sz){
	if (sz==1) return;
	upd_lazy(node*2+1,segtree[node].lazy,sz/2);
	upd_lazy(node*2+2,segtree[node].lazy,sz/2);
	segtree[node].lazy=0;
	upd_chmin(node*2+1,segtree[node].max1,sz/2);
	upd_chmin(node*2+2,segtree[node].max1,sz/2);
	upd_chmax(node*2+1,segtree[node].min1,sz/2);
	upd_chmax(node*2+2,segtree[node].min1,sz/2);
}
SegTreeBeats(int n){
	segtree.resize(tol(ceil(log2(n)+1))-1);
	for (int i = segtree.size()/2-1; i >= 0; i--){
		merge(i);
	}
}
SegTreeBeats(vector<T> v){
	segtree.resize(tol(ceil(log2(v.size())+1))-1);
	for (int i = 0; i < v.size(); i++){
		segtree[i+segtree.size()/2].sum=segtree[i+segtree.size()/2].max1=segtree[i+segtree.size()/2].min1=v[i];
	}
	for (int i = segtree.size()/2-1; i >= 0; i--){
		merge(i);
	}
}
void chmin(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
	if (r==-1) r = segtree.size()/2;
	if (l>tarr || r<tarl || val>=segtree[node].max1) return;
	if (l>=tarl && r<=tarr && val>segtree[node].max2){
		upd_chmin(node,val,r-l+1);
		return;
	}
	dallan(node,r-l+1);
	int mid = l+(r-l)/2;
	chmin(tarl, tarr, val, l, mid, node*2+1);
	chmin(tarl, tarr, val, mid+1, r, node*2+2);
	merge(node);
}
void chmax(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
	if (r==-1) r = segtree.size()/2;
	if (l>tarr || r<tarl || val<=segtree[node].min1) return;
	if (l>=tarl && r<=tarr && val<segtree[node].min2){
		upd_chmax(node,val,r-l+1);
		return;
	}
	dallan(node,r-l+1);
	int mid = l+(r-l)/2;
	chmax(tarl, tarr, val, l, mid, node*2+1);
	chmax(tarl, tarr, val, mid+1, r, node*2+2);
	merge(node);
}
void update(int tarl, int tarr, int val, int l = 0, int r = -1, int node = 0){
	if (r==-1) r = segtree.size()/2;
	if (l>=tarl && r<=tarr) {
		upd_lazy(node,val,r-l+1);
		return;
	}
	if (l>tarr || r<tarl) return;
	dallan(node,r-l+1);
	int mid = l+(r-l)/2;
	update(tarl, tarr, val, l, mid, node*2+1);
	update(tarl, tarr, val, mid+1, r, node*2+2);
	merge(node);
}
int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
	if (r==-1) r = segtree.size()/2;
	if (l>=tarl && r<=tarr) return segtree[node].sum;
	if (l>tarr || r<tarl) return 0;
	dallan(node,r-l+1);
	int mid = l+(r-l)/2;
	int lnode = query(tarl, tarr, l, mid, node*2+1);
	int rnode = query(tarl, tarr, mid+1, r, node*2+2);
	return lnode+rnode;
}
};//SegTreeBeats
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
	if (*max_element(l.begin(), l.end())==0 && *min_element(r.begin(), r.end())==c.size()-1){
		int n = c.size();
		int q = v.size();
		vector<int> suff(q);
		vector<int> pref(q);
		vector<int> mava(q);
		vector<int> miva(q);
		vector<pair<int,int>> arr(n);
		for (int i = 0; i < n; i++){
			arr[i]={c[i],i};
		}
		sortarr(arr);
		for (int i = 0; i < q; i++){
			pref[i]=suff[i]=v[i];
			if (i) pref[i]+=pref[i-1];
		}
		mava.back()=miva.back()=pref.back();
		for (int i = q-2; i >= 0; i--){
			miva[i]=min(miva[i+1],pref[i]);
			mava[i]=max(mava[i+1],pref[i]);
			suff[i]+=suff[i+1];
		}
		int lel = 0;
		int crq = 0;
		vector<int> rval(n,-23);
		for (int i = n-1; i >= 0; i--){
			int crr = min(lel,arr[i].first);
			int kk = 0;
			if (crq) kk=pref[crq-1];
			while (crq<q && ((crr+(mava[crq]-kk)>=arr[i].first) || (crr+(miva[crq]-kk)<=0))) {
				crr+=v[crq];
				crr=min(crr,arr[i].first);
				crr=max(crr,0ll);
				kk=pref[crq];
				crq++;
			}
			kk=0;
			if (crq<q) kk=suff[crq];
			rval[arr[i].second]=crr+kk;
			lel=crr;
		}
		return normalize(rval);
	}
	int n = c.size(), q = l.size();
	if (*min_element(c.begin(),c.end())!=*max_element(c.begin(), c.end())){
		if (n<=2000 && q<=2000){
			vector<int> arr(n);
			for (int i = 0; i < q; ++i)
			{
				for (int j = l[i]; j <= r[i]; j++){
					arr[j]+=v[i];
					if (arr[j]<0) arr[j]=0;
					if (arr[j]>c[j]) arr[j]=c[j];
				}
			}
			return normalize(arr);
		}
		LSegTree segtree(n);
		for (int i = 0; i < q; ++i)
		{
			segtree.update(l[i],r[i],v[i]);
		}
		vector<int> arr(n,0);
		for (int i = 0; i < n; ++i)
		{
			arr[i]=segtree.query(i,i);
			if (arr[i]<0) arr[i]=0;
			if (arr[i]>c[i]) arr[i]=c[i];
		}
		return normalize(arr);
	}
	SegTreeBeats<int> segtree(n);
	for (int i = 0; i < q; i++){
		segtree.update(l[i],r[i],v[i]);
		segtree.chmin(l[i],r[i],c[0]);
		segtree.chmax(l[i],r[i],0);
	}
	vector<int> arr(n);
	for (int i = 0; i < n; i++){
		arr[i]=segtree.query(i,i);
	}
	return normalize(arr);
}

Compilation message

candies.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:227:77: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |  if (*max_element(l.begin(), l.end())==0 && *min_element(r.begin(), r.end())==c.size()-1){
      |                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
candies.cpp: In instantiation of 'std::vector<int> normalize(std::vector<_Tp>&) [with T = long long int]':
candies.cpp:268:24:   required from here
candies.cpp:20:123: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (int i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
      |                                                                                                                         ~~^~~~~~~~~~~
candies.cpp: In instantiation of 'SegTreeBeats<T>::Node::Node() [with T = long long int]':
/usr/include/c++/10/bits/stl_construct.h:109:7:   required from 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = SegTreeBeats<long long int>::Node; _Args = {}]'
/usr/include/c++/10/bits/stl_uninitialized.h:567:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = SegTreeBeats<long long int>::Node*; _Size = long unsigned int; bool _TrivialValueType = false]'
/usr/include/c++/10/bits/stl_uninitialized.h:623:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = SegTreeBeats<long long int>::Node*; _Size = long unsigned int]'
/usr/include/c++/10/bits/stl_uninitialized.h:685:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = SegTreeBeats<long long int>::Node*; _Size = long unsigned int; _Tp = SegTreeBeats<long long int>::Node]'
/usr/include/c++/10/bits/vector.tcc:627:35:   required from 'void std::vector<_Tp, _Alloc>::_M_default_append(std::vector<_Tp, _Alloc>::size_type) [with _Tp = SegTreeBeats<long long int>::Node; _Alloc = std::allocator<SegTreeBeats<long long int>::Node>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:940:4:   required from 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = SegTreeBeats<long long int>::Node; _Alloc = std::allocator<SegTreeBeats<long long int>::Node>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
candies.cpp:162:16:   required from 'SegTreeBeats<T>::SegTreeBeats(long long int) [with T = long long int]'
candies.cpp:298:29:   required from here
candies.cpp:80:27: warning: 'SegTreeBeats<long long int>::Node::min1' will be initialized after [-Wreorder]
   80 |  T sum, lazy, max1, max2, min1, min2, maxc, minc;
      |                           ^~~~
candies.cpp:80:21: warning:   'long long int SegTreeBeats<long long int>::Node::max2' [-Wreorder]
   80 |  T sum, lazy, max1, max2, min1, min2, maxc, minc;
      |                     ^~~~
candies.cpp:81:2: warning:   when initialized here [-Wreorder]
   81 |  Node():sum(0),lazy(0),max1(0),min1(0),max2(-INF),min2(INF),minc(1),maxc(1){}
      |  ^~~~
candies.cpp:80:45: warning: 'SegTreeBeats<long long int>::Node::minc' will be initialized after [-Wreorder]
   80 |  T sum, lazy, max1, max2, min1, min2, maxc, minc;
      |                                             ^~~~
candies.cpp:80:39: warning:   'long long int SegTreeBeats<long long int>::Node::maxc' [-Wreorder]
   80 |  T sum, lazy, max1, max2, min1, min2, maxc, minc;
      |                                       ^~~~
candies.cpp:81:2: warning:   when initialized here [-Wreorder]
   81 |  Node():sum(0),lazy(0),max1(0),min1(0),max2(-INF),min2(INF),minc(1),maxc(1){}
      |  ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 17100 KB Output is correct
2 Correct 353 ms 21296 KB Output is correct
3 Correct 391 ms 21004 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 172 ms 8280 KB Output is correct
3 Correct 130 ms 39272 KB Output is correct
4 Correct 546 ms 47624 KB Output is correct
5 Correct 686 ms 48016 KB Output is correct
6 Correct 886 ms 48404 KB Output is correct
7 Correct 783 ms 47744 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 56 ms 11236 KB Output is correct
4 Correct 78 ms 7404 KB Output is correct
5 Correct 122 ms 18284 KB Output is correct
6 Correct 128 ms 18284 KB Output is correct
7 Correct 129 ms 18280 KB Output is correct
8 Correct 121 ms 18280 KB Output is correct
9 Correct 116 ms 18284 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 434 ms 17100 KB Output is correct
7 Correct 353 ms 21296 KB Output is correct
8 Correct 391 ms 21004 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 172 ms 8280 KB Output is correct
11 Correct 130 ms 39272 KB Output is correct
12 Correct 546 ms 47624 KB Output is correct
13 Correct 686 ms 48016 KB Output is correct
14 Correct 886 ms 48404 KB Output is correct
15 Correct 783 ms 47744 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 56 ms 11236 KB Output is correct
19 Correct 78 ms 7404 KB Output is correct
20 Correct 122 ms 18284 KB Output is correct
21 Correct 128 ms 18284 KB Output is correct
22 Correct 129 ms 18280 KB Output is correct
23 Correct 121 ms 18280 KB Output is correct
24 Correct 116 ms 18284 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Incorrect 122 ms 13608 KB Output isn't correct
27 Halted 0 ms 0 KB -