제출 #1290575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290575		hiepsimauhong	Birthday gift (IZhO18_treearray)	C++20	56 / 100	4101 ms	155972 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define FOR(I, L, R) for(int I(L); I <= (int)R ; ++I)
#define FOD(I, R, L) for(int I(R); I >= (int)L ; --I)
#define FOA(I, A) for(auto &I : A)

#define print(A, L, R) FOR(I, L, R){cout << A[I] <<' ';} cout << '\n';
#define printz(A, L, R) FOR(I, 1, L){FOR(J, 1, R){if(A[I][J] <= -oo / 10) cout << "- "; else cout << A[I][J] << ' ';} cout << '\n';} cout << '\n';
#define prints(A) FOA(I, A) cout << I <<' '; cout << '\n';

#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(A) A.begin(), A.end()
#define quickly cin.tie(0) -> ios_base::sync_with_stdio(0);
#define FILE "robot"

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e18;

int n, m, q;
int a[N];
vector<int> g[N];

struct LCA{
        int st[N], en[N], h[N], el;
        ii e[2 * N], rmq[2 * N][20];

        void build(int u, int par){
                st[u] = ++el;
                e[el] = {h[u], u};

                FOA(v, g[u]){
                        if(v == par){
                                continue;
                        }
                        h[v] = h[u] + 1;
                        build(v, u);
                        e[++el] = {h[u], u};
                }
                en[u] = el;
        }

        void buildRMQ(){
                FOR(i, 1, 2 * n - 1){
                        rmq[i][0] = e[i];
                }

                for(int j(1) ; (1 << j) <= 2 * n - 1 ; ++j){
                        for(int i(1) ; i + (1 << j) - 1 <= 2 * n - 1 ; ++i){
                                rmq[i][j] = min(rmq[i + (1 << j - 1)][j - 1], rmq[i][j - 1]);
                        }
                }
        }

        bool acs(int u, int v){
                if(st[v] <= st[u] && st[u] <= en[v]){
                        return 1;
                }
                return 0;
        }

        int get(int u, int v){
                if(u == 0) return v;
                if(v == 0) return u;

                int l = st[u];
                int r = st[v];

                if(l > r) swap(l, r);

                int k = __lg(r - l + 1);

                return min(rmq[l][k], rmq[r - (1 << k) + 1][k]).sd;
        }
} lca;

struct SegmentTree{
        int sg[N << 2];

        void update(int id, int l, int r, int pos, int val){
                if(l > pos || r < pos){
                        return;
                }
                if(l == r){
                        sg[id] = val;
                        return;
                }

                int mid = (l + r) >> 1;

                update(id << 1, l, mid, pos, val);
                update(id << 1 | 1, mid + 1, r, pos, val);

                sg[id] = lca.get(sg[id << 1], sg[id << 1 | 1]);
        }

        int get(int id, int l, int r, int u, int v){
                if(l > v || r < u){
                        return 0;
                }
                if(u <= l && r <= v){
                        return sg[id];
                }

                int mid = (l + r) >> 1;

                return lca.get(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
        }
} sg;

signed main(){ quickly
        if(fopen(FILE".inp", "r")){
                freopen(FILE".inp", "r", stdin);
                freopen(FILE".out", "w", stdout);
        }

        cin >> n >> m >> q;

        FOR(i, 1, n - 1){
                int u, v;
                cin >> u >> v;

                g[u].push_back(v);
                g[v].push_back(u);
        }

        lca.build(1, -1);
        lca.buildRMQ();

        FOR(i, 1, m){
                int x;
                cin >> x;
                sg.update(1, 1, m, i, x);
        }

        while(q--){
                int type;
                cin >> type;

                if(type == 1){
                        int pos, val;
                        cin >> pos >> val;

                        sg.update(1, 1, m, pos, val);
                }
                else{
                        int l, r, u;
                        cin >> l >> r >> u;

                        bool check = 0;

                        int j = l;
                        FOR(i, l, r){
                                while(j <= i){
                                        int v = sg.get(1, 1, m, j, i);
                                        if(lca.acs(v, u)){
                                                break;
                                        }
                                        else{
                                                ++j;
                                        }
                                }

                                if(sg.get(1, 1, m, j, i) == u){
                                        cout << j <<' ' << i << '\n';
                                        check = 1;
                                        break;
                                }
                        }

                        if(!check){
                                cout << -1 <<' ' << -1 << '\n';
                        }
                }
        }
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'int main()':
treearray.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen(FILE".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen(FILE".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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