이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |