Submission #1031008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031008		pera	Sprinkler (JOI22_sprinkler)	C++17	9 / 100	4032 ms	105156 KiB

sprinkler

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 1;
int n , M , Q , o = 0;
vector<int> t(4 * N) , lz(4 * N) , H(N) , in(N) , out(N) , d(N) , id(N) , up(N) , order = {0};
vector<vector<int>> g(N) , E(N) , D(N);
void dfs(int u , int p = 0){
   order.push_back(u);
   up[u] = p;
   in[u] = ++o;
   d[u] = d[p] + 1;
   E[d[u]].push_back(in[u]);
   if(u != 1){
      g[u].erase(find(g[u].begin() , g[u].end() , p));
   }
   for(int x = 0;x < (int)g[u].size();x ++){
      dfs(g[u][x] , u);
   }
   out[u] = o;
}
void build(int u , int l , int r){
   t[u] = lz[u] = 1;
   if(l != r){
      int m = (l + r) / 2;
      build(u * 2 , l , m);
      build(u * 2 + 1 , m + 1 , r);
   }
}
void push(int u){
   t[u * 2] = t[u * 2] * lz[u] % M;
   t[u * 2 + 1] = t[u * 2 + 1] * lz[u] % M;
   lz[u * 2] = lz[u * 2] * lz[u] % M;
   lz[u * 2 + 1] = lz[u * 2 + 1] * lz[u] % M;
   lz[u] = 1;
}
void upd(int u , int l , int r , int L , int R , int w){
   if(l > r || r < L || l > R){
      return ;
   }
   if(L <= l && r <= R){
      int bf = t[u];
      t[u] = t[u] * w % M;
      lz[u] = lz[u] * w % M;
      return;
   }
   int m = (l + r) / 2;
   push(u);
   upd(u * 2 , l , m , L , R , w);
   upd(u * 2 + 1 , m + 1 , r , L , R , w);
}
int get(int u , int l , int r , int pos){
   if(l == r){
      return t[u];
   }
   int m = (l + r) / 2;
   push(u);
   if(pos <= m){
      return get(u * 2 , l , m , pos);
   }
   return get(u * 2 + 1 , m + 1 , r , pos);
}
int GET(int u){
   return get(1 , 1 , n , id[u]);
}
void UPD(int u , int x , int W){
   for(int depth = d[u];depth <= min(d[u] + x , n);depth ++){
      //[in[u] , out[u]] -> id[first] , id[last];
      int L = -1 , R = -1;
      for(int bit = 20;bit >= 0;bit --){
         if(L + (1 << bit) < (int)E[depth].size()){
            if(E[depth][L + (1 << bit)] < in[u]){
               L += (1 << bit);
            }
         }
         if(R + (1 << bit) < (int)E[depth].size()){
            if(E[depth][R + (1 << bit)] <= out[u]){
               R += (1 << bit);
            }
         }
      }
      ++L;
      if(0 <= min(L , R) && max(L , R) < (int)E[depth].size() && in[u] <= min(E[depth][L] , E[depth][R]) && max(E[depth][L] , E[depth][R]) <= out[u] && L <= R){
         upd(1 , 1 , n , D[depth][L] , D[depth][R] , W);
      }
   }
   if(u != 1){
      int cnt = x , v = u , lst;
      while(v != 1 && cnt > 0){
         H[up[v]] = H[up[v]] * W % M;
         lst = v;
         v = up[v];
         --cnt;
         for(int depth = d[v] + 1;depth <= min(n , d[v] + cnt);depth ++){
            int posL = -1 , posR = -1;
            int subL = -1 , subR = -1;
            for(int bit = 20;bit >= 0;bit --){
               if(posL + (1 << bit) < (int)E[depth].size()){
                  if(E[depth][posL + (1 << bit)] < in[lst]){
                     posL += (1 << bit);
                  }
               }
               if(subL + (1 << bit) < (int)E[depth].size()){
                  if(E[depth][subL + (1 << bit)] < in[v]){
                     subL += (1 << bit);
                  }
               }
               if(subR + (1 << bit) < (int)E[depth].size()){
                  if(E[depth][subR + (1 << bit)] <= out[v]){
                     subR += (1 << bit);
                  }
               }
               if(posR + (1 << bit) < (int)E[depth].size()){
                  if(E[depth][posR + (1 << bit)] <= out[lst]){
                     posR += (1 << bit);
                  }
               }
            }
            ++subL;
            ++posR;
            if(posL >= subL){
               upd(1 , 1 , n , D[depth][subR] , D[depth][posL] , W);
            }
            if(posR <= subR){
               upd(1 , 1 , n , D[depth][posR] , D[depth][subR] , W);
            }
         }
      }
   }
}
main(){
   cin >> n >> M;
   for(int i = 1;i < n;i ++){
      int u , v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs(1);
   build(1 , 1 , n);
   o = 0;
   for(int a = 1;a <= n;a ++){
      for(int x : E[a]){
         id[order[x]] = ++o;
         D[a].push_back(id[order[x]]);
      }
   }
   for(int i = 1;i <= n;i ++){
      cin >> H[i];
   }
   cin >> Q;
   while(Q--){
      int e;
      cin >> e;
      if(e == 1){
         int x , d , W;
         cin >> x >> d >> W;
         UPD(x , d , W);
      }else{
         int x;
         cin >> x; 
         cout << H[x] * GET(x) % M << endl;
      }
   }
}

Compilation message (stderr)

sprinkler.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int, long long int)':
sprinkler.cpp:42:11: warning: unused variable 'bf' [-Wunused-variable]
   42 |       int bf = t[u];
      |           ^~
sprinkler.cpp: At global scope:
sprinkler.cpp:131:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  131 | main(){
      | ^~~~

• Subtask 1: 0 / 3
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17