Submission #568281

#	Time	Username	Problem	Language	Result	Execution time	Memory
568281		tqbfjotld	Sprinkler (JOI22_sprinkler)	C++14	41 / 100	4053 ms	110652 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

long long L;

long long arr[200005];
int inv[200005];
int ord[200005];

struct node{
    int s,e;
    long long v;
    long long lazy;
    node *l,*r;
    node (int _s, int _e){
        s = _s; e = _e;
        if (s==e){
            v = arr[inv[s]];
        }
        else{
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
        lazy = 1;
    }
    void proc(){
        if (lazy==1){
            return;
        }
        v *= lazy;
        v %= L;
        if (s==e) {
            lazy = 1;
            return;
        }
        l->lazy *= lazy;
        l->lazy %= L;
        r->lazy *= lazy;
        r->lazy %= L;
        lazy = 1;
    }
    void add(int a, int b, long long val){
        if (b<a) return;
        proc();
        if (a<=s && e<=b){
            lazy *= val;
            lazy %= L;
            proc();
            return;
        }
        if (b<=(s+e)/2){
            l->add(a,b,val);
        }
        else if (a>(s+e)/2){
            r->add(a,b,val);
        }
        else{
            l->add(a,b,val);
            r->add(a,b,val);
        }
        l->proc();
        r->proc();
    }
    long long qu(int pos){
        proc();
        if (s==e) return v;
        if (pos<=(s+e)/2) return l->qu(pos);
        else return r->qu(pos);
    }
}*root;

int cur = 1;
bool vis[200005];
int p[200005];
vector<int> adjl[200005];
int minch[200005][45];
int maxch[200005][45];

int main(){
    int n;
    scanf("%d%lld",&n,&L);
    memset(minch,-1,sizeof(minch));
    for (int x = 0; x<n-1; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        adjl[a].push_back(b);
        adjl[b].push_back(a);
    }
    for (int x = 1; x<=n; x++){
        scanf("%lld",&arr[x]);
    }
    queue<int> q;
    p[1] = 0;
    q.push(1);
    while (!q.empty()){
        int nd = q.front();
        q.pop();
        if (vis[nd]){
            continue;
        }
        vis[nd] = true;
        ord[nd] = cur++;
        inv[ord[nd]] = nd;
        for (auto x : adjl[nd]){
            if (!vis[x]){
                p[x] = nd;
                q.push(x);
            }
        }
    }
    for (int x = 1; x<=n; x++){
        int c = x;
        for (int y = 0; y<=40; y++){
            if (c!=0){
                //printf("thing %d %d = %d\n",c,y,ord[x]);
                if (minch[c][y]==-1) minch[c][y] = ord[x];
                minch[c][y] = min(minch[c][y],ord[x]);
                maxch[c][y] = max(maxch[c][y],ord[x]);
            }
            c = p[c];
        }
    }
    root = new node(1,n);
    int Q;
    scanf("%d",&Q);
    while (Q--){
        int type;
        scanf("%d",&type);
        if (type==1){
            int a,b;
            long long c;
            scanf("%d%d%lld",&a,&b,&c);
            int ex1,ex2;

            for (int x = 0; x<=b; x++){
                //printf("a = %d, x = %d\n",a,x);
                if (minch[a][x]==-1) break;
                //printf("add %d %d\n",minch[a][x],maxch[a][x]);
                root->add(minch[a][x],maxch[a][x],c);
            }

            for (int y = 1; y<=b; y++){
                int ch = a;
                a = p[a];
                if (a==0) break;
                for (int x = 0; x<=b-y; x++){
                    if (minch[a][x]==-1) break;
                    if (x==0 || minch[ch][x-1]==-1){
                        //printf("addd %d %d\n",minch[a][x],maxch[a][x]);
                        root->add(minch[a][x],maxch[a][x],c);
                    }
                    else{
                        //printf("a a = %d, x = %d\n",a,x);
                        if (minch[a][x]==-1) break;
                        //printf("add %d %d\n",minch[a][x],minch[ch][x-1]-1);
                        root->add(minch[a][x],minch[ch][x-1]-1,c);
                        //printf("add %d %d\n",maxch[ch][x-1]+1,maxch[a][x]);
                        root->add(maxch[ch][x-1]+1,maxch[a][x],c);
                    }
                }
            }
        }
        else{
            int a;
            scanf("%d",&a);
            printf("%lld\n",root->qu(ord[a]));
        }
    }
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:133:17: warning: unused variable 'ex1' [-Wunused-variable]
  133 |             int ex1,ex2;
      |                 ^~~
sprinkler.cpp:133:21: warning: unused variable 'ex2' [-Wunused-variable]
  133 |             int ex1,ex2;
      |                     ^~~
sprinkler.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d%lld",&n,&L);
      |     ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         scanf("%lld",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
sprinkler.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |             scanf("%d%d%lld",&a,&b,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:165:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~

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