제출 #568281

#제출 시각아이디문제언어결과실행 시간메모리
568281tqbfjotldSprinkler (JOI22_sprinkler)C++14
41 / 100
4053 ms110652 KiB
#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])); } } }

컴파일 시 표준 에러 (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);
      |             ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...