Submission #754441

#	Time	Username	Problem	Language	Result	Execution time	Memory
754441		tolbi	사탕 분배 (IOI21_candies)	C++17	67 / 100	886 ms	48404 KiB

candies

#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 (stderr)

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33