제출 #44021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44021		Nordway	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2124 ms	262144 KiB

treearray

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#include <assert.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define low_b lower_bound
#define up_b upper_bound
#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef set<int> si;

const int N = 2 * 1e+5 + 111;
const int mxn = 1e+6 + 111;

vi g[mxn];
int a[mxn], lvl[mxn], up[mxn][18], d[mxn];
si cnt[N], L[N];

inline void dfs(int v, int p){
    lvl[v] = lvl[p] + 1;
    up[v][0] = p;
    for(int i = 1; i <= 17; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    d[v] = 1;
    for(auto to : g[v]){
        if(to == p)continue;
        dfs(to, v);
        d[v] += d[to];
    }
}

inline int lca(int x, int y){
    if(lvl[x] > lvl[y]) swap(x, y);
    for(int i = 17; i >= 0; i--){
        if(lvl[up[y][i]] >= lvl[x])y = up[y][i];
    }
    if(x == y)return x;
    for(int i = 17; i >= 0; i--){
        if(up[y][i] != up[x][i]){
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++){
        cin >> a[i];
        cnt[a[i]].insert(i);
        if(i != 1){
            L[lca(a[i], a[i - 1])].insert(i - 1);
        }
    }
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int pos, v;
            cin >> pos >> v;
            cnt[a[pos]].erase(pos);
            if(pos != 1){
                L[lca(a[pos], a[pos - 1])].erase(pos - 1);
            }
            if(pos != n){
                L[lca(a[pos], a[pos + 1])].erase(pos);
            }
            a[pos] = v;
            cnt[v].insert(pos);
            if(pos != 1){
                L[lca(a[pos - 1], a[pos])].insert(pos - 1);
            }
            if(pos != n){
                L[lca(a[pos], a[pos + 1])].insert(pos);
            }
        }
        else{
            int l, r, v;
            cin >> l >> r >> v;
            if(!cnt[v].empty()){
                auto i = cnt[v].low_b(l);
                if(i != cnt[v].end()){
                    int ans = *i;
                    if(ans <= r){
                        cout << ans << " " << ans << endl;
                        continue;
                    }
                }
            }
            if (!L[v].empty()) {
				auto i = L[v].lower_bound(l);
				if (i != L[v].end()) {
					int ans = *i;
					if (ans + 1 <= r) {
						cout << ans << " " << ans + 1 << endl;
				    	continue;
					}
				}
			}
			cout << "-1 -1" << endl;
        }
    }
}

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