oj.uz

Submission #1031008

# Submission time Handle Problem Language Result Execution time Memory
1031008 2024-07-22T13:26:32 Z pera Sprinkler (JOI22_sprinkler) C++17
9 / 100
 4000 ms 105156 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 72260 KB Output is correct
2 Correct 30 ms 72284 KB Output is correct
3 Correct 33 ms 72436 KB Output is correct
4 Incorrect 40 ms 72568 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72436 KB Output is correct
2 Correct 1000 ms 89352 KB Output is correct
3 Correct 899 ms 86464 KB Output is correct
4 Correct 870 ms 96192 KB Output is correct
5 Correct 877 ms 87956 KB Output is correct
6 Correct 909 ms 86980 KB Output is correct
7 Correct 925 ms 87020 KB Output is correct
8 Correct 754 ms 87408 KB Output is correct
9 Correct 918 ms 105156 KB Output is correct
10 Correct 914 ms 100036 KB Output is correct
11 Correct 840 ms 89284 KB Output is correct
12 Correct 756 ms 86304 KB Output is correct
13 Correct 846 ms 87744 KB Output is correct
14 Correct 775 ms 87000 KB Output is correct
15 Correct 778 ms 85920 KB Output is correct
16 Correct 756 ms 85696 KB Output is correct
17 Correct 737 ms 86084 KB Output is correct
18 Correct 28 ms 72280 KB Output is correct
19 Correct 30 ms 72276 KB Output is correct
20 Correct 30 ms 72272 KB Output is correct
21 Correct 27 ms 72284 KB Output is correct
22 Correct 28 ms 72284 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72436 KB Output is correct
2 Correct 1000 ms 89352 KB Output is correct
3 Correct 899 ms 86464 KB Output is correct
4 Correct 870 ms 96192 KB Output is correct
5 Correct 877 ms 87956 KB Output is correct
6 Correct 909 ms 86980 KB Output is correct
7 Correct 925 ms 87020 KB Output is correct
8 Correct 754 ms 87408 KB Output is correct
9 Correct 918 ms 105156 KB Output is correct
10 Correct 914 ms 100036 KB Output is correct
11 Correct 840 ms 89284 KB Output is correct
12 Correct 756 ms 86304 KB Output is correct
13 Correct 846 ms 87744 KB Output is correct
14 Correct 775 ms 87000 KB Output is correct
15 Correct 778 ms 85920 KB Output is correct
16 Correct 756 ms 85696 KB Output is correct
17 Correct 737 ms 86084 KB Output is correct
18 Correct 28 ms 72280 KB Output is correct
19 Correct 30 ms 72276 KB Output is correct
20 Correct 30 ms 72272 KB Output is correct
21 Correct 27 ms 72284 KB Output is correct
22 Correct 28 ms 72284 KB Output is correct
23 Correct 28 ms 72284 KB Output is correct
24 Incorrect 888 ms 89180 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 72276 KB Output is correct
2 Correct 2877 ms 102028 KB Output is correct
3 Execution timed out 4032 ms 101832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 72528 KB Output is correct
2 Incorrect 2967 ms 98096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 72260 KB Output is correct
2 Correct 30 ms 72284 KB Output is correct
3 Correct 33 ms 72436 KB Output is correct
4 Incorrect 40 ms 72568 KB Output isn't correct
5 Halted 0 ms 0 KB -