Submission #571385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571385	2022-06-02T06:27:04 Z	kshitij_sodani	Distributing Candies (IOI21_candies)	C++17	Compilation error	0 ms	0 KB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'

#include "candies.h"
#include <vector>
llo tree[4*200001][4];
llo lazy[4*200001];
//min
//max
//max-min
vector<pair<int,int>> pre[200001];
vector<pair<int,int>> pre2[200001];
llo vis[200001];
void push(int no,int l,int r){
	tree[no][0]+=lazy[no];
	tree[no][1]+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
}
void update(int no,int l,int r,int aa,int bb,int x){
	push(no,l,r);
	if(l>bb or r<aa or aa>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]+=x;
		push(no,l,r);
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x);
		update(no*2+2,mid+1,r,aa,bb,x);
		tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
		tree[no][2]=min(tree[no*2+1][2],tree[no*2+2][2]);
		tree[no][2]=min(tree[no][2],tree[no*2+2][0]-tree[no*2+1][1]);
		tree[no][3]=max(tree[no*2+1][3],tree[no*2+2][3]);
		tree[no][3]=max(tree[no][3],tree[no*2+2][1]-tree[no*2+1][0]);
	}
}
llo query(int no,int l,int r,int aa,int bb){
	push(no,l,r);
	if(r<aa or l>bb or aa>bb){
		return (llo)1e18;
	}
	if(aa<=l and r<=bb){
		return tree[no][0];
	}
	int mid=(l+r)/2;
	return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
   	vector<int> ans;
    int q=l.size();
    for(int i=0;i<q;i++){
    	pre[l[i]].pb({i,v[i]});
    }
    for(int i=0;i<q;i++){
    	pre2[r[i]].pb({i,v[i]});
    }
    llo su=0;
    for(int i=0;i<n;i++){
    	for(auto j:pre[i]){
    		update(0,0,q,j.a+1,q,j.b);
    		su+=j.b;
            vis[j.a+1]=j.b;
    	}
    	llo ind=0;
    	if(tree[0][2]<=-c[i]){
    		llo no=0;
    		pair<llo,llo> cur={0,q};
    		llo ma=0;
    		while(cur.a<cur.b){
    			int mid=(cur.a+cur.b)/2;
    			llo ok=0;
    			if(tree[no*2+2][0]-tree[no*2+1][1]<=-c[i]){
    				ok=1;
    			}
    			if(tree[no*2+2][2]<=-c[i]){
    				ok=1;
    			}
    			if(tree[no*2+2][0]-ma<=-c[i]){
    				ok=1;
    			}
    			if(ok==1){
    				ma=max(ma,tree[no*2+1][1]);
    				cur={mid+1,cur.b};
    				no*=2;
    				no+=2;
    				continue;
    			}
    			cur={cur.a,mid};
    			no=no*2+1;
    		}
    		if(tree[no][0]-ma<=-c[i]){
    			ind=cur.a;
    		}
    	}
    	llo ind2=0;
    	if(tree[0][3]>=c[i]){
    		//ans.pb(c[i]);
    		llo no=0;
    		pair<llo,llo> cur={0,q};
    		llo ma=0;
    		while(cur.a<cur.b){
    			/*if(i==2){
    				cout<<cur.a<<","<<cur.b<<endl;
    			}*/
    			/*if(i==1){
    				cout<<cur.a<<","<<cur.b<<":"<<ma<<endl;
    			}*/
    			
    			int mid=(cur.a+cur.b)/2;
    			push(no,cur.a,cur.b);
    			push(no*2+1,cur.a,mid);
    			push(no*2+2,mid+1,cur.b);

    			llo ok=0;
    			if(tree[no*2+2][1]-tree[no*2+1][0]>=c[i]){
    				ok=1;
    			}
    			/*if(i==2){
    				cout<<ok<<','<<endl;
    				cout<<tree[no*2+2][1]-tree[no*2+1][0]<<"::"<<endl;
    			}*/
    			if(tree[no*2+2][3]>=c[i]){
    				ok=1;
    			}
    		/*	if(i==2){
    				cout<<ok<<','<<endl;
    			}*/
    			if(tree[no*2+2][1]-ma>=c[i]){
    				ok=1;
    			}
    			/*if(i==2){
    				cout<<ok<<','<<endl;
    			}*/
    			if(ok==1){
    				ma=min(ma,tree[no*2+1][0]);
    				cur={mid+1,cur.b};

    				no*=2;
    				no+=2;
    				continue;
    			}
    			cur={cur.a,mid};
    			no=no*2+1;
    		}
    	
    		if(i==2){
    			//cout<<no<<",,"<<endl;
    			//cout<<tree[no][1]<<",,"<<ma<<endl;
    		}
    		if(tree[no][1]-ma>=c[i]){
    			ind2=cur.a;
    		}

    		//cout<<11<<endl;
    	}
    	else{
    		//ans.pb(tree[0][3]);
    	}
    	//cout<<i<<":"<<ind<<":"<<ind2<<endl;
    	//ans.pb(min(su,(llo)c[i]));
    	llo ind3=0;
        llo cot=0;
        llo ind4=0;
        for(int j=0;j<=q;j++){
            cot+=vis[j];
            cot=max(cot,(llo)0);
            cot=min(cot,c[i]);
            if(cot==c[i]){
                ind3=max(ind3,j);
            }
            if(cot==0){
                ind4=max(ind4,j);
            }
        }
        assert(ind2==ind3);
        ans.pb(cot);
        if(ind2>ind){
    		llo ans2=c[i]+su-query(0,0,q,ind2,ind2);
    		//ans.pb(ans2);
    	}
    	else{
    		llo ans2=su-query(0,0,q,ind,ind);
    		//ans.pb(ans2);
    	}
    
    	for(auto j:pre2[i]){
    		
            update(0,0,q,j.a+1,q,-j.b);
    		vis[j.a+1]=0;
            su-=j.b;
    	}
    }


    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:181:29: error: no matching function for call to 'min(llo&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
  181 |             cot=min(cot,c[i]);
      |                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
candies.cpp:181:29: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  181 |             cot=min(cot,c[i]);
      |                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
candies.cpp:181:29: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  181 |             cot=min(cot,c[i]);
      |                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
candies.cpp:181:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  181 |             cot=min(cot,c[i]);
      |                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
candies.cpp:181:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  181 |             cot=min(cot,c[i]);
      |                             ^
candies.cpp:183:32: error: no matching function for call to 'max(llo&, int&)'
  183 |                 ind3=max(ind3,j);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
candies.cpp:183:32: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  183 |                 ind3=max(ind3,j);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
candies.cpp:183:32: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  183 |                 ind3=max(ind3,j);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
candies.cpp:183:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  183 |                 ind3=max(ind3,j);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
candies.cpp:183:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  183 |                 ind3=max(ind3,j);
      |                                ^
candies.cpp:186:32: error: no matching function for call to 'max(llo&, int&)'
  186 |                 ind4=max(ind4,j);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
candies.cpp:186:32: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  186 |                 ind4=max(ind4,j);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
candies.cpp:186:32: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  186 |                 ind4=max(ind4,j);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
candies.cpp:186:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  186 |                 ind4=max(ind4,j);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
candies.cpp:186:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  186 |                 ind4=max(ind4,j);
      |                                ^
candies.cpp:192:11: warning: unused variable 'ans2' [-Wunused-variable]
  192 |       llo ans2=c[i]+su-query(0,0,q,ind2,ind2);
      |           ^~~~
candies.cpp:196:11: warning: unused variable 'ans2' [-Wunused-variable]
  196 |       llo ans2=su-query(0,0,q,ind,ind);
      |           ^~~~