Submission #1053222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1053222	2024-08-11T09:51:45 Z	epicci23	Distributing Candies (IOI21_candies)	C++17	Compilation error	0 ms	0 KB

candies

#include "bits/stdc++.h"
#include "candies.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const long long INF = 1e18;

struct SegT_Min{
  int n;
  vector<long long> t;
  SegT_Min(int nn){
   n=nn;
   t.assign(4*n+5,INF);
  }
  void upd(int rt,int l,int r,int ind,int u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	  t[rt]=min(t[rt],u);
  	  return;
  	}
  	int m=(l+r)/2;
  	upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
  	t[rt]=min(t[rt*2],t[rt*2+1]);
  }
  long long query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return INF;
  	if(l>=gl && r<=gr) return t[rt];
  	int m=(l+r)/2;
  	return min(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};

struct SegT_Max{
  int n;
  vector<long long> t;
  SegT_Max(int nn){
   n=nn;
   t.assign(4*n+5,-INF);
  }
  void upd(int rt,int l,int r,int ind,int u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	  t[rt]=max(t[rt],u);
  	  return;
  	}
  	int m=(l+r)/2;
  	upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
  	t[rt]=max(t[rt*2],t[rt*2+1]);
  }
  long long query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return -INF;
  	if(l>=gl && r<=gr) return t[rt];
  	int m=(l+r)/2;
  	return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};


vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n=sz(c),q=sz(V);
    vector<int> ans(n);
    vector<array<int,2>> c;
    for(int i=0;i<n;i++) c.push_back({C[i],i});
    sort(all(c));
    long long pre[q+5];
    pre[0]=0;
    for(int i=1;i<=q;i++) pre[i]=pre[i-1]+V[i-1];
    SegT_Min t1(q);SegT_Max t2(q);
    for(int i=0;i<=q;i++){
     t1.upd(1,1,q,i,pre[i]);
     t2.upd(1,1,q,i,pre[i]);
    }

    int p=0;
    long long cur=0;
  for(int i=n-1;i>=0;i--){
  	int cap=c[i][0];
  	cur=min(cur,cap);
  	while(p<q){
	    int l=p+1,r=q+1;
	    while(l<r){
	      int m=(l+r)/2;
	      if(t1.query(1,1,q,p+1,m)<=pre[p]-cur) r=m;
	      else l=m+1;
	    }
	    int ans0=l;
	    l=p+1,r=q+1;
	    while(l<r){
	     int m=(l+r)/2;
	     if(t2.query(1,1,q,p+1,m)>=cap-cur-pre[p]) r=m;
	     else l=m+1;
	    }
	    int ansm=l;
	    if(ansm==q+1 && ans0==q+1) break;
	    p=min(ansm,ans0);
	    if(ans0<=ansm) cur=0;
	    else cur=cap;
    }
    ans[c[i][1]]=cur+pre[q]-pre[p];
  }
  return ans;
}



/*void _(){
  int n,q;
  cin >> n >> q;
  vector<array<int,2>> c;
  for(int i=1;i<=n;i++){
  	int a;cin >> a;
  	c.push_back({a,i});
  }
  int xd[q+5],ans[n+5],pre[q+5];
  pre[0]=0;
  for(int i=1;i<=q;i++){
  	cin >> xd[i];
    pre[i]=pre[i-1]+xd[i];
  }
  sort(all(c));
  SegT_Min t1(q);SegT_Max t2(q);
  for(int i=0;i<=q;i++){
    t1.upd(1,1,q,i,pre[i]);
    t2.upd(1,1,q,i,pre[i]);
  }

  int p=0,cur=0;
  for(int i=n-1;i>=0;i--){
  	int cap=c[i][0];
  	cur=min(cur,cap);
  	while(p<q){
	    int l=p+1,r=q+1;
	    while(l<r){
	      int m=(l+r)/2;
	      if(t1.query(1,1,q,p+1,m)<=pre[p]-cur) r=m;
	      else l=m+1;
	    }
	    int ans0=l;
	    l=p+1,r=q+1;
	    while(l<r){
	     int m=(l+r)/2;
	     if(t2.query(1,1,q,p+1,m)>=cap-cur-pre[p]) r=m;
	     else l=m+1;
	    }
	    int ansm=l;
	    if(ansm==q+1 && ans0==q+1) break;
	    p=min(ansm,ans0);
	    if(ans0<=ansm) cur=0;
	    else cur=cap;
    }
    ans[c[i][1]]=cur+pre[q]-pre[p];
  }

  for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Compilation message

candies.cpp: In member function 'void SegT_Min::upd(int, int, int, int, int)':
candies.cpp:20:23: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int&)'
   20 |      t[rt]=min(t[rt],u);
      |                       ^
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:20:23: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   20 |      t[rt]=min(t[rt],u);
      |                       ^
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:20:23: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   20 |      t[rt]=min(t[rt],u);
      |                       ^
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:20:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   20 |      t[rt]=min(t[rt],u);
      |                       ^
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:20:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   20 |      t[rt]=min(t[rt],u);
      |                       ^
candies.cpp: In member function 'void SegT_Max::upd(int, int, int, int, int)':
candies.cpp:45:23: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int&)'
   45 |      t[rt]=max(t[rt],u);
      |                       ^
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:45:23: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   45 |      t[rt]=max(t[rt],u);
      |                       ^
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:45:23: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   45 |      t[rt]=max(t[rt],u);
      |                       ^
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:45:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   45 |      t[rt]=max(t[rt],u);
      |                       ^
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:45:23: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   45 |      t[rt]=max(t[rt],u);
      |                       ^
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:62:14: error: 'c' was not declared in this scope
   62 |     int n=sz(c),q=sz(V);
      |              ^
candies.cpp:5:20: note: in definition of macro 'sz'
    5 | #define sz(a) (int)a.size()
      |                    ^
candies.cpp:67:19: error: 'q' was not declared in this scope
   67 |     long long pre[q+5];
      |                   ^
candies.cpp:68:5: error: 'pre' was not declared in this scope
   68 |     pre[0]=0;
      |     ^~~
candies.cpp:80:19: error: no matching function for call to 'min(long long int&, int&)'
   80 |    cur=min(cur,cap);
      |                   ^
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:80:19: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   80 |    cur=min(cur,cap);
      |                   ^
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:80:19: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   80 |    cur=min(cur,cap);
      |                   ^
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:80:19: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   80 |    cur=min(cur,cap);
      |                   ^
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:80:19: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   80 |    cur=min(cur,cap);
      |                   ^