제출 #1242199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242199		Dedibeat	Birthday gift (IZhO18_treearray)	C++20	100 / 100	402 ms	88220 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << endl;
}
template<typename T>
void print(T *begin, const T *end)
{
    for(T *it = begin; it < end; it++)
        cout << *it << " ";
    cout << endl;
}
int n, l, m, q;
vector<vector<int>> adj;

int timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}



struct container{
    vector<set<int>> con;
    vector<int> v;
    container(vector<int> v, int mx) : v(v)
    {
        con.assign(mx + 100, set<int>());
        for(int i = 0; i < v.size(); i++)
            con[v[i]].insert(i);
    }

    void upd(int pos, int x)
    {
        int prev = v[pos];
        con[prev].erase(pos);
        con[x].insert(pos);
        v[pos] = x;
    }

    int get(int l, int r, int x)
    {
        auto it = con[x].lower_bound(l);
        if(it != con[x].end() && *it <= r) 
            return *it;
        else return -1;
    }
};


int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL);
    cin >> n >> m >> q;
    adj.assign(n, vector<int>());
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    preprocess(0);
    vector<int> a(m);
    for(int i = 0; i < m; i++)
        cin >> a[i], a[i]--;

    vector<int> b(m);
    for(int i = 1; i < m; i++)
        b[i] = lca(a[i - 1], a[i]);

    container conA(a, n), conB(b, n);
    while(q--)
    {
        int type;
        cin >> type;
        //cout << "q " <<  type << ": \n";
        if(type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            pos--, val--;
            a[pos] = val;
            conA.upd(pos, val);
            if(pos > 0) 
            {
                b[pos] = lca(a[pos - 1], a[pos]);
                conB.upd(pos, b[pos]);
            }
            if(pos < m - 1) 
            {
                b[pos + 1] = lca(a[pos], a[pos + 1]);
                conB.upd(pos + 1, b[pos + 1]);
            }
        }
        else 
        {
            int lo, hi, v;
            cin >> lo >> hi >> v;
            lo--, hi--, v--;
            
            // for(int i = lo; i <= hi; i++)
            // {
            //     if(a[i] == v) 
            //     {
            //         cout << i + 1 << " " << i + 1 << "\n";
            //         goto endloop;
            //     }
            //     if(i > lo && b[i] == v) 
            //     {
            //         cout << i << " " << i + 1 << "\n";
            //         goto endloop;
            //     }

            // }
            int x1 = conA.get(lo ,hi, v), x2 = conB.get(lo + 1, hi, v);
            if(x1 != -1) cout << x1 + 1 << ' ' << x1 + 1 << "\n";
            else if(x2 != -1) cout << x2 << " " << x2 + 1 << "\n";
            else cout << "-1 -1\n";

            // cout << "-1 -1\n";
            // endloop:
            // continue;
        }
    }
}

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