제출 #1224903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224903		minhpk	Sprinkler (JOI22_sprinkler)	C++20	컴파일 에러	0 ms	0 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
int a,mod;
vector <int> z[1000005];
int h[1000005];
int sta[1000005];
int fin[1000005];
int tour;
vector <int> depth[1000005];
int par[1000005];
int high[1000005];
int base[1000005];
int maxdepth=0;
int cur=1;
bool cmp(int a,int b){
     return a<b;
}

int sbd(int i){
    int res=base[high[i]];
    int t=high[i];

    int pre=lower_bound(depth[t].begin(),depth[t].end(),sta[i])-depth[t].begin()+1;

    if (pre+base[t]>a || pre+base[t]>a){
            cout << i << " " << t << " " << depth[t].size() << "\n";
    }
    res+=pre;
    return res;
}

void dfs(int i,int j,int k){
    par[i]=j;
    tour++;
    sta[i]=tour;
    maxdepth=max(maxdepth,k);
    depth[k].push_back(sta[i]);

    for (auto p:z[i]){
         if (p==j){
            continue;
         }
         high[p]=high[i]+1;
         dfs(p,i,k+1);
    }

    fin[i]=tour;
}

int f[4000005];
int lazy[4000005];
pair<int,int> length[1000005];
void push(int id){
    if (lazy[id]!=1){
        lazy[id*2]*=lazy[id];
        lazy[id*2+1]*=lazy[id];
        lazy[id*2]%=mod;
        lazy[id*2+1]%=mod;

        f[id*2]*=lazy[id];
        f[id*2+1]*=lazy[id];
        f[id*2]%=mod;
        f[id*2+1]%=mod;

        lazy[id]=1;
    }
}

void update(int id,int l,int r,int x,int y,int val){
     if (x>r || y<l){
         return;
     }
     if (l>=x && y>=r){
         f[id]*=val;
         f[id]%=mod;
         lazy[id]=(lazy[id]*val)%mod;
         return;
     }
     int mid=(l+r)/2;
     push(id);
     update(id*2,l,mid,x,y,val);
     update(id*2+1,mid+1,r,x,y,val);
     f[id]=f[id*2]+f[id*2+1];
}
int get(int id,int l,int r,int pos){
    if (l==r){
        return f[id];
    }
    int mid=(l+r)/2;
    push(id);
    if (pos<=mid){
        return get(id*2,l,mid,pos);
    }else{
        return get(id*2+1,mid+1,r,pos);
    }
}






void queryup(int n,int d,int w){
    int cnt=0;
    while (cnt<=d && n!=0){
         int t=high[n];
//         if (cur==1){
//             cout << n << "\n";
//         }
         for (int i=0;i<=d-cnt;i++){
              int pre=t+i;
              if (pre>maxdepth){
                  continue;
              }

              int len1=length[pre].second-length[pre].first;
//              if ( cur==1&& pre==4){
//                  cout << "ok" << " " <<fin[n]-sta[n] << "\n";
//              }
              int len2=fin[n]-sta[n];
              if (len1<len2){
                  length[pre]={sta[n],fin[n]};
              }
         }

         cnt++;
         n=par[n];
    }
}





void query1(int x,int d,int w){
    int t=high[x];
    for (int i=0;i<=d;i++){
         if (t-i<=0){
            break;
         }
         int sta1=t-i;
         int pos1=lower_bound(depth[sta1].begin(),depth[sta1].end(),length[t-i].first)-depth[sta1].begin()+1+base[sta1];
         int pos2=upper_bound(depth[sta1].begin(),depth[sta1].end(),length[t-i].second)-depth[sta1].begin()+base[sta1];
         if (pos1<=pos2){
             update(1,1,a,pos1,pos2,w);
         }
    }

    for (int i=1;i<=d;i++){
         if (t+i>maxdepth){
            break;
         }
         int sta1=t+i;
         int pos1=lower_bound(depth[sta1].begin(),depth[sta1].end(),length[sta1].first)-depth[sta1].begin()+1+base[sta1];
         int pos2=upper_bound(depth[sta1].begin(),depth[sta1].end(),length[sta1].second)-depth[sta1].begin()+base[sta1];
         if (pos1<=pos2){
             update(1,1,a,pos1,pos2,w);
         }
    }
}

signed main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> mod;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    for (int i=1;i<=a;i++){
         cin >> h[i];
    }
    dfs(1,0,1);
    for (int i=1;i<=maxdepth;i++){
         base[i]=base[i-1]+depth[i-1].size();
         sort(depth[i].begin(),depth[i].end(),cmp);
    }
    for (int i=1;i<=a;i++){
         high[i]++;
    }
    for (int i=1;i<=4*a+5;i++){
         lazy[i]=1;
         f[i]=1;
    }

    int q;
    cin >> q;


    while (q--){
         int c;
         cin >> c;
         if (c==2){
             int x;
             cin >> x;
             int pos=sbd(x);
             int pre=get(1,1,a,pos);

             cout << (h[x]*pre)%mod << "\n";

         }else{
             int x,d,w;
             cin >> x >> d >> w;
              int t=high[x];
             for (int i=0;i<=d;i++){
                  length[max(t-i,1LL)]={0,-1};
                  length[t+i]={0,-1};
             }

             queryup(x,d,w);

             query1(x,d,w);
              t=high[x];
             for (int i=0;i<=d;i++){
                  length[max(t-i,1LL)]={0,-1};
                  length[t+i]={0,-1};
             }
         }




    }


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:211:29: error: no matching function for call to 'max(int, long long int)'
  211 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from sprinkler.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:211:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  211 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from sprinkler.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:211:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  211 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from sprinkler.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:211:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  211 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from sprinkler.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:211:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  211 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
sprinkler.cpp:220:29: error: no matching function for call to 'max(int, long long int)'
  220 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from sprinkler.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:220:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  220 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from sprinkler.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:220:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  220 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from sprinkler.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:220:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  220 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from sprinkler.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:220:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  220 |                   length[max(t-i,1LL)]={0,-1};
      |                          ~~~^~~~~~~~~