結果
問題 | No.1030 だんしんぐぱーりない |
ユーザー | autumn-eel |
提出日時 | 2020-04-17 22:54:26 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 2,261 bytes |
コンパイル時間 | 2,534 ms |
コンパイル使用メモリ | 174,388 KB |
実行使用メモリ | 26,872 KB |
最終ジャッジ日時 | 2024-04-14 15:13:01 |
合計ジャッジ時間 | 9,698 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
24,180 KB |
testcase_01 | AC | 9 ms
23,444 KB |
testcase_02 | AC | 10 ms
24,380 KB |
testcase_03 | AC | 9 ms
24,392 KB |
testcase_04 | AC | 10 ms
23,872 KB |
testcase_05 | AC | 173 ms
26,788 KB |
testcase_06 | AC | 146 ms
25,900 KB |
testcase_07 | AC | 108 ms
25,780 KB |
testcase_08 | AC | 109 ms
24,940 KB |
testcase_09 | AC | 147 ms
26,764 KB |
testcase_10 | AC | 77 ms
24,852 KB |
testcase_11 | AC | 167 ms
24,916 KB |
testcase_12 | AC | 157 ms
26,820 KB |
testcase_13 | AC | 132 ms
26,156 KB |
testcase_14 | AC | 181 ms
26,260 KB |
testcase_15 | AC | 107 ms
24,016 KB |
testcase_16 | AC | 156 ms
25,160 KB |
testcase_17 | AC | 144 ms
26,332 KB |
testcase_18 | AC | 197 ms
26,448 KB |
testcase_19 | AC | 113 ms
24,732 KB |
testcase_20 | AC | 124 ms
24,832 KB |
testcase_21 | AC | 134 ms
26,244 KB |
testcase_22 | AC | 126 ms
25,344 KB |
testcase_23 | AC | 152 ms
26,068 KB |
testcase_24 | AC | 136 ms
24,512 KB |
testcase_25 | AC | 144 ms
25,368 KB |
testcase_26 | AC | 105 ms
24,336 KB |
testcase_27 | AC | 121 ms
24,480 KB |
testcase_28 | AC | 174 ms
25,608 KB |
testcase_29 | AC | 123 ms
26,608 KB |
testcase_30 | AC | 116 ms
25,176 KB |
testcase_31 | AC | 119 ms
25,556 KB |
testcase_32 | AC | 158 ms
25,760 KB |
testcase_33 | AC | 154 ms
26,072 KB |
testcase_34 | AC | 77 ms
24,432 KB |
testcase_35 | AC | 240 ms
26,816 KB |
testcase_36 | AC | 239 ms
26,704 KB |
testcase_37 | AC | 243 ms
26,764 KB |
testcase_38 | AC | 240 ms
26,872 KB |
testcase_39 | AC | 240 ms
26,596 KB |
testcase_40 | AC | 10 ms
25,084 KB |
testcase_41 | AC | 11 ms
24,176 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<n;i++) using namespace std; typedef long long ll; typedef pair<int,int>P; const int MOD=1000000007; const int INF=0x3f3f3f3f; const ll INFL=0x3f3f3f3f3f3f3f3f; #define N (1<<18) template<class T> struct RMQ{ pair<T,int>dat[2*N]; T inf; function<pair<T,int>(pair<T,int>,pair<T,int>)>merge; RMQ(T Inf,function<pair<T,int>(pair<T,int>,pair<T,int>)>Merge){ inf=Inf;merge=Merge; rep(i,2*N-1){ dat[i].first=inf; if(i>=N-1)dat[i].second=i-N+1; } } void update(int k,T x){ k+=N-1; dat[k].first=x; while(k){ k=(k-1)/2; dat[k]=merge(dat[k*2+1],dat[k*2+2]); } } pair<T,int>query(int a,int b,int k=0,int l=0,int r=N){ if(b<=l||r<=a)return make_pair(inf,-1); if(a<=l&&r<=b)return dat[k]; auto lb=query(a,b,k*2+1,l,(l+r)/2); auto rb=query(a,b,k*2+2,(l+r)/2,r); return merge(lb,rb); } T getValue(int a,int b){ return query(a,b).first; } int getIndex(int a,int b){ return query(a,b).second; } }; template<class T> pair<T,int>RangeMax(pair<T,int>a,pair<T,int>b){ return a.first>=b.first?a:b; } template<class T> pair<T,int>RangeMin(pair<T,int>a,pair<T,int>b){ return a.first<=b.first?a:b; } RMQ<int>seg1(INT_MAX,RangeMin<int>);//euler tour RMQ<int>seg2(INT_MAX,RangeMin<int>);//euler tour id min RMQ<int>seg3(0,RangeMax<int>);//euler tour id max int c[200000]; vector<int>E[200000]; int d[200000]; int ans[200000]; int a[200000]; int vid[200000]; int vs[200000]; int vcnt=0; void dfs(int v,int p,int Max){ vid[v]=vcnt; vs[vcnt++]=v; if(p!=-1)d[v]=d[p]+1; Max=max(Max,c[v]); ans[v]=Max; for(int u:E[v]){ dfs(u,v,Max); vs[vcnt++]=v; } } int main(){ int n,K,q;cin>>n>>K>>q; rep(i,n)scanf("%d",&c[i]); rep(i,K)scanf("%d",&a[i]),a[i]--; rep(i,n-1){ int a,b;scanf("%d%d",&a,&b);a--;b--; E[b].push_back(a); } dfs(0,-1,0); rep(i,vcnt){ seg1.update(i,d[vs[i]]); } rep(i,K){ seg2.update(i,vid[a[i]]); seg3.update(i,vid[a[i]]); } rep(i,q){ int ty;scanf("%d",&ty); if(ty==1){ int x,y;scanf("%d%d",&x,&y);x--;y--; seg2.update(x,vid[y]); seg3.update(x,vid[y]); } else{ int l,r;scanf("%d%d",&l,&r);l--; int L=seg2.getValue(l,r),R=seg3.getValue(l,r); int id=vs[seg1.getIndex(L,R+1)]; printf("%d\n",ans[id]); } } }