Submission #712180

#	Time	Username	Problem	Language	Result	Execution time	Memory
712180		Ahmed57	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1452 ms	88900 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N=2e5+5;
ordered_set s[N];
set<int> v[N];
vector<int> adj[N];
int P[N][18],hi[N];
int n;vector<int>  nodes;
void dfs(int node,int pa){
    P[node][0]=pa;
    hi[node]=hi[pa]+1;
    for(int k=1;k<=17;k++)
        P[node][k]=P[P[node][k-1]][k-1];
    for(int i:adj[node])
    {
        if(i==pa) continue;
        dfs(i,node);
    }
}
int lca(int x,int y){
    if(hi[x]<hi[y]) swap(x,y);
    for(int k=17;k>=0;k--)
    {
        if(hi[x]-(1<<k) >= hi[y])
            x=P[x][k];
    }
    if(x==y) return x;
    for(int k=17;k>=0;k--)
    {
        if(P[x][k] != P[y][k])
            x=P[x][k],y=P[y][k];
    }
    return P[x][0];
}
void remn(int i){
    auto it = v[nodes[i]].lower_bound(i);
    v[nodes[i]].erase(it);
}
void addn(int i){
    v[nodes[i]].insert(i);
}
void add(int i){
    s[lca(nodes[i],nodes[i+1])].insert(i);
}void rem(int i){
    auto it = s[lca(nodes[i],nodes[i+1])].lower_bound(i);
    s[lca(nodes[i],nodes[i+1])].erase(it);
}
signed main(){
    scanf("%d",&n);
    int k,q;cin>>k>>q;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    for(int i = 0;i<k;i++){
        int x;cin>>x;
        nodes.push_back(x);
    }
    for(int i = 0;i<k-1;i++){add(i);addn(i);}
    addn(k-1);
    while(q--){
        int ty;cin>>ty;
        if(ty==1){
            int pos,val;
            cin>>pos>>val;
            pos--;
            remn(pos);
            if(pos>0)rem(pos-1);
            if(pos<k-1)rem(pos);
            nodes[pos] = val;
            if(pos>0)add(pos-1);
            if(pos<k-1)add(pos);
            addn(pos);
        }else{
            int l,r,vv;cin>>l>>r>>vv;
            l--;r--;
            int rr = s[vv].order_of_key(r);
            int ll = s[vv].order_of_key(l);
            int val = rr-ll;
            if(val>0){
                cout<<*s[vv].find_by_order(ll)+1<<" "<<*s[vv].find_by_order(ll)+2<<"\n";
            }else {
                auto it = v[vv].lower_bound(l);
                if(it!=v[vv].end()&&*it<=r){
                    cout<<*it+1<<" "<<*it+1<<endl;
                }else{
                    cout<<-1<<" "<<-1<<endl;
                }
            }
        }
    }
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
treearray.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44