| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 888979 | 2023-12-18T14:26:13 Z | amirhoseinfar1385 | Sprinkler (JOI22_sprinkler) | C++17 | Compilation error |
0 ms | 0 KB |
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
vector<long long>adj[maxn];
long long q,high[maxn],n,mod,timea=0,part[maxn];
pair<long long,long long>stf[maxn];
struct segment{
vector<long long>seg;
long long sz=0;
void create(){
while(__builtin_popcount(sz)!=1){
sz++;
}
seg.resize(sz*2,1);
}
void add(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i]*=w;
seg[i]%=mod;
return ;
}
long long m=(l+r)>>1;
add((i<<1),l,m,tl,tr,w);
add((i<<1)^1,m+1,r,tl,tr,w);
return ;
}
long long pors(long long i){
if(i==0){
return 1;
}
long long ret=pors((i>>1))*seg[i]%mod;
return ret;
}
}seg[maxn];
vector<pair<long long,long long>>alll[maxn];
void pre(long long u=1,long long par=1){
part[u]=par;
timea++;
stf[u].first=timea;
alll[high[u]].push_back(make_pair(stf[u].first,u));
for(auto x:adj[u]){
if(x!=par){
high[x]=high[u]+1;
pre(x,u);
}
}
stf[u].second=timea;
}
void upd(long long u,long long dis,long long w){
long long z=0;
long long lev=high[u]+dis;
while(lev>=0&&high[u]<=lev){
if(lev<maxn){
long long l=lower_bound(alll[lev].begin(),alll[lev].end(),make_pair(stf[u].first,-1))-alll[lev].begin();
long long r=lower_bound(alll[lev].begin(),alll[lev].end(),make_pair(stf[u].second+1,-1))-alll[lev].begin();
//cout<<u<<" "<<dis<<" "<<w<<" "<<l<<" "<<r<<" "<<lev<<endl;
r--;
seg[lev].add(1,0,seg[lev].sz-1,l,r,w);
}
if(z==1){
u=part[u];
lev--;
z=0;
}
else{
lev--;
z=1;
}
}
}
void solve(long long u){
long long ind=lower_bound(alll[high[u]].begin(),alll[high[u]].end(),make_pair(stf[u].first,u))-alll[high[u]].begin();
//cout<<u<<" wtf "<<ind<<endl;
cout<<seg[high[u]].pors(ind+seg[high[u]].sz)<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>mod;
for(long long i=0;i<n-1;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
pre(1);
for(long long i=0;i<maxn;i++){
seg[i].sz=alll[i].size();
seg[i].create();
}
for(long long i=1;i<=n;i++){
long long d;
cin>>d;
upd(i,0,d);
}
cin>>q;
for(long long i=0;i<q;i++){
long long qq;
cin>>qq;
if(qq==1){
long long u,d,w;
cin>>u>>d>>w;
upd(u,d,w);
}
else{
long long u;
cin>>u;
solve(u);
}
}
}
Compilation message
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Value = const std::pair<long long int, int>]':
/usr/include/c++/10/bits/stl_algobase.h:1324:14: required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Tp = std::pair<long long int, int>; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/10/bits/stl_algobase.h:1359:32: required from '_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Tp = std::pair<long long int, int>]'
sprinkler.cpp:59:88: required from here
/usr/include/c++/10/bits/predefined_ops.h:67:22: error: no match for 'operator<' (operand types are 'std::pair<long long int, long long int>' and 'const std::pair<long long int, int>')
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1075:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1075 | operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1075:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1156:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
1156 | operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1156:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1249:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
1249 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1249:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1323:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
1323 | operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1323:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1417:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
1417 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1417:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1492:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
1492 | operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1492:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'const std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from sprinkler.cpp:1:
/usr/include/c++/10/bits/regex.h:1592:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
1592 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1592:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:489:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
489 | operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:489:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: deduced conflicting types for parameter '_T2' ('long long int' and 'int')
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
366 | operator<(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:404:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
404 | operator<(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:404:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1451 | operator<(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1507:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1507 | operator<(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1507:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
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 sprinkler.cpp:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'std::pair<long long int, long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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 sprinkler.cpp:1:
/usr/include/c++/10/string_view:544:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator<(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
544 | operator< (basic_string_view<_CharT, _Traits> __x,
|