oj.uz

답안 #754205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754205 2023-06-07T08:41:04 Z tolbi 사탕 분배 (IOI21_candies) C++17
38 / 100
 838 ms 48452 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) {
	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 instantiation of 'std::vector<int> normalize(std::vector<_Tp>&) [with T = long long int]':
candies.cpp:239: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:17:   required from 'SegTreeBeats<T>::SegTreeBeats(long long int) [with T = long long int]'
candies.cpp:255:29:   required from here
candies.cpp:80:28: 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:22: warning:   'long long int SegTreeBeats<long long int>::Node::max2' [-Wreorder]
   80 |   T sum, lazy, max1, max2, min1, min2, maxc, minc;
      |                      ^~~~
candies.cpp:81:3: 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:46: 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:40: warning:   'long long int SegTreeBeats<long long int>::Node::maxc' [-Wreorder]
   80 |   T sum, lazy, max1, max2, min1, min2, maxc, minc;
      |                                        ^~~~
candies.cpp:81:3: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 21972 KB Output is correct
2 Correct 337 ms 21192 KB Output is correct
3 Correct 325 ms 21080 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 199 ms 8276 KB Output is correct
3 Correct 127 ms 39184 KB Output is correct
4 Correct 525 ms 47660 KB Output is correct
5 Correct 654 ms 48068 KB Output is correct
6 Correct 838 ms 48452 KB Output is correct
7 Correct 712 ms 47788 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 81 ms 7628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 371 ms 21972 KB Output is correct
7 Correct 337 ms 21192 KB Output is correct
8 Correct 325 ms 21080 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 199 ms 8276 KB Output is correct
11 Correct 127 ms 39184 KB Output is correct
12 Correct 525 ms 47660 KB Output is correct
13 Correct 654 ms 48068 KB Output is correct
14 Correct 838 ms 48452 KB Output is correct
15 Correct 712 ms 47788 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 81 ms 7628 KB Output isn't correct
19 Halted 0 ms 0 KB -