Submission #568285

#	Time	Username	Problem	Language	Result	Execution time	Memory
568285		tqbfjotld	Sprinkler (JOI22_sprinkler)	C++14	41 / 100	4077 ms	108244 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 || a==-1) return;
        //if (s==1 && e==4) printf("add %d %d\n",a,b);
        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);
            for (int x = 0; x<=b; x++){
                //printf("x = %d\n",x);
                root->add(minch[a][b-x],maxch[a][b-x],c);
                if (b-x!=0) root->add(minch[a][b-x-1],maxch[a][b-x-1],c);

                a = p[a];
                if (a==0){
                    a = 1;
                    b--;
                }
            }

}
        else{
            int a;
            scanf("%d",&a);
            printf("%lld\n",root->qu(ord[a]));
        }
    }
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d%lld",&n,&L);
      |     ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%lld",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         scanf("%d",&type);
      |         ~~~~~^~~~~~~~~~~~
sprinkler.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |             scanf("%d%d%lld",&a,&b,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:149:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |             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