Submission #862106

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
862106	2023-10-17T14:11:48 Z	sunwukong123	Distributing Candies (IOI21_candies)	C++17	Compilation error	0 ms	0 KB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 

struct node {
    int s,e,m,lazy;
    pi val,mn,mx;
    node *l, *r;
    node(int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        lazy=0;
        val=mx={0,s};
        mn={0,-s};
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void value(){
        if(lazy==0)return;
        if(s==e){
            mn.first+=lazy;
            mx.first+=lazy;
            val.first+=lazy;
            lazy=0;
            return ;
        }
        val.first+=lazy;
        mn.first+=lazy;
        mx.first+=lazy;
        l->lazy+=lazy;
        r->lazy+=lazy;
        lazy=0;
        return;
    }
    void update(int x, int y, int nval){
        value();
        if(s==x&&e==y){
            lazy+=nval;
            return;
        }
        if(x>m)r->update(x,y,nval);
        else if(y<=m)l->update(x,y,nval);
        else l->update(x,m,nval),r->update(m+1,y,nval);
        l->value(),r->value();
        mn=min(l->mn,r->mn);
        mx=max(l->mx,r->mx);
        val=l->val+r->val;
    }
    int query(int x, int y){
        value();
        if(s==x&&e==y)return val.first;
        if(x>m)return r->query(x,y);
        else if(y<=m)return l->query(x,y);
        else return l->query(x,m) + query(m+1,y);
    }
    pi query_max(int x, int y){
        value();
        if(s==x&&e==y)return mx;
        if(x>m)return r->query_max(x,y);
        else if(y<=m)return l->query_max(x,y);
        else return max(l->query_max(x,m), r->query_max(m+1,y));
    }
    pi query_min(int x, int y){
        value();
        if(s==x&&e==y)return mn;
        if(x>m)return r->query_min(x,y);
        else if(y<=m)return l->query_min(x,y);
        else return min(l->query_min(x,m), r->query_min(m+1,y));
    }

}*seg;

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();
    vector<pi> A[n+5];
    int Q=l.size();
    seg=new node(0,Q+3); // 0 is just set to 0 for everything
    for(int t=0;t<Q;t++){
        A[l[t]].push_back({v[t],t+1});
        A[r[t]+1].push_back({-v[t],t+1});
    }
    vector<int32_t>res;
    for(int i=0;i<=n-1;i++){
        //debug(i);
        for(auto x:A[i]){
            //debug(x.first,x.second);
            seg->update(x.second,Q+3,x.first);
        }

        int lo=0,hi=Q+2;
        while(lo<hi-1){
            int mi=(lo+hi)/2;
            pi MX=seg->query_max(mi,Q+3);
            pi MN=seg->query_min(mi,Q+3);
            if(MX.first-MN.first>=c[i]){
                lo=mi;
            } else{
                hi=mi;
            }
        }
        pi MN=seg->query_min(lo,Q+3);
        pi MX=seg->query_max(lo,Q+3);
        MN.second*=-1;
        int F=seg->query(Q+3,Q+3);

        if(MN.second>=MX.second){
            res.push_back(F-MN.first);
        } else {
            res.push_back(c[i]+(F-MX.first));
        }
    }
    return res;
}

Compilation message

candies.cpp: In member function 'void node::update(long long int, long long int, long long int)':
candies.cpp:59:19: error: no match for 'operator+' (operand types are 'pi' {aka 'std::pair<long long int, long long int>'} and 'pi' {aka 'std::pair<long long int, long long int>'})
   59 |         val=l->val+r->val;
      |             ~~~~~~^~~~~~~
      |                |      |
      |                |      pair<[...],[...]>
      |                pair<[...],[...]>
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:508:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)'
  508 |     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:508:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from candies.h:1,
                 from candies.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)'
 1540 |     operator+(typename move_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::move_iterator<_IteratorL>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6022:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6022 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6022:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:56,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.tcc:1160:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1160 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1160:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   mismatched types 'const _CharT*' and 'std::pair<long long int, long long int>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:56,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.tcc:1180:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1180 |     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.tcc:1180:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6059:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 6059 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6059:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6075:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, _CharT)'
 6075 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6075:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6087:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6087 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6087:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6093:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6093 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6093:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6099:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6099 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6099:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6121:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6121 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6121:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   mismatched types 'const _CharT*' and 'std::pair<long long int, long long int>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6127:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6127 |     operator+(_CharT __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6127:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6133:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const _CharT*)'
 6133 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6133:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6139:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, _CharT)'
 6139 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6139:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/complex:331:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator+(const std::complex<_Tp>&, const std::complex<_Tp>&)'
  331 |     operator+(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:331:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::complex<_Tp>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/complex:340:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator+(const std::complex<_Tp>&, const _Tp&)'
  340 |     operator+(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:340:5: note:   template argument deduction/substitution failed:
candies.cpp:59:23: note:   'pi' {aka 'std::pair<long long int, long long int>'} is not derived from 'const std::complex<_Tp>'
   59 |         val=l->val+r->val;
      |                       ^~~
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from candies.cpp:2:
/usr/include/c++/10/complex:349:5: note: candidate: 'template<class _Tp> std::complex<_Tp> st