oj.uz

답안 #1100575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100575 2024-10-14T09:15:18 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
56 / 100
 835 ms 117912 KB 
// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define fx cout << fixed << setprecision(4);
#define md (tl+tr)/2
#define TL v+v, tl,md
#define TR v+v+1, md+1,tr
#define Tl t[v].l, tl,md
#define Tr t[v].r, md+1,tr
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) (x).begin(), (x).end()
#define int ll
#define cnk(n,k) mod(mod(f[(n)]*binpow(f[(n)-(k)],M-2))*binpow(f[(k)],M-2))
#define cnkf(n,k) mod(mod(f[(n)]*inv[(n)-(k)])*inv[(k)])

using namespace std;

typedef complex<double> cd;

struct mine{int l;int r;int i;};
struct edge{int u;int v;int w;};
struct tree{int l;int r;int val;};

auto cmp = [](mine a, mine b) { return a.i<b.i; };

mt19937 RR((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 
int random(int l, int r){
  return uniform_int_distribution<int>(l, r)(RR);
}

int M=998244353;

int mod1(int a,int b=M) {
    if (a<0)
        a=b+a%b;
    return a % b;
}

int binpow(int a,int n,int m=M) {
    a=mod1(a,m);
    if (!n)
        return 1;
    if (n&1)
        return (a * binpow(a,n-1))%m;
    int x = binpow(a,n>>1);
    return (x*x)%m; 
}

const ll INF=1e18+7;
const int N=3e5+7;

int n,m,q,p[N][20],tin[N],tout[N],tick,a[N];
set <int> s[N],t[N];
vector <int> g[N];

void dfs(int v) {
    tin[v]=++tick;
    for (int i=1;i<20;i++)
        p[v][i]=p[p[v][i-1]][i-1];
    for (auto to : g[v]) {
        if (to!=p[v][0]) {
            p[to][0]=v;
            dfs(to);
        }
    }
    tout[v]=tick;
}

bool isp(int u,int v) {
    return tin[u]<=tin[v] and tout[v]<=tout[u];
}

int lca(int u,int v) {
    if (isp(u,v))
        return u;
    if (isp(v,u))
        return v;
    for (int i=19;i>=0;i--) {
        if (p[v][i] and !isp(p[v][i],u))
            v=p[v][i];
    }
    return p[v][0];
}

void add(int i) {
    if (i>1)
        s[lca(a[i-1],a[i])].insert(i);
    if (i<n)
        s[lca(a[i],a[i+1])].insert(i+1);
    t[a[i]].insert(i);
}

void del(int i) {
    if (i>1)
        s[lca(a[i-1],a[i])].erase(i);
    if (i<n)
        s[lca(a[i],a[i+1])].erase(i+1);
    t[a[i]].erase(i);
}

void solve() {
    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);
    for (int i=1;i<=m;i++) {
        cin >> a[i];
        add(i);
    }
    while (q--) {
        int tp,l,r,v;
        cin >> tp;
        if (tp==1) {
            cin >> l >> v;
            del(l);
            a[l]=v;
            add(l);
        } else {
            cin >> l >> r >> v;
            auto it=t[v].lower_bound(l);
            if (it!=t[v].end() and *it<=r) {
                cout << *it << ' ' << *it << '\n';
            } else {
                it=s[v].upper_bound(l);
                if (it!=s[v].end() and *it<=r)
                    cout << *it-1 << ' ' << *it << '\n';
                else
                    cout << -1 << ' ' << -1 << '\n';
            }
        }
    }
} 

signed main() {
    // freopen("triangles.in", "r", stdin);
    // freopen("triangles.out", "w", stdout);
    // fx
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
            count++;
        }
    }
    return 0;
}

// ctrl + shift + p make stress isis__Good isis__Generator
// g++ -std=c++17 (path) -o run
// .\run

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39504 KB n=5
2 Correct 7 ms 39680 KB n=100
3 Correct 8 ms 39504 KB n=100
4 Correct 8 ms 39640 KB n=100
5 Correct 7 ms 39504 KB n=100
6 Correct 7 ms 39504 KB n=100
7 Correct 7 ms 39504 KB n=100
8 Correct 7 ms 39648 KB n=100
9 Correct 7 ms 39516 KB n=100
10 Correct 8 ms 39504 KB n=100
11 Correct 6 ms 39504 KB n=100
12 Correct 6 ms 39504 KB n=100
13 Correct 6 ms 39504 KB n=100
14 Correct 6 ms 39504 KB n=100
15 Correct 6 ms 39504 KB n=100
16 Correct 6 ms 39504 KB n=100
17 Correct 6 ms 39504 KB n=100
18 Correct 6 ms 39672 KB n=100
19 Correct 8 ms 39504 KB n=100
20 Correct 6 ms 39504 KB n=100
21 Correct 7 ms 39816 KB n=100
22 Correct 6 ms 39504 KB n=100
23 Correct 6 ms 39504 KB n=100
24 Correct 6 ms 39672 KB n=100
25 Correct 6 ms 39504 KB n=100
26 Correct 6 ms 39504 KB n=12
27 Correct 7 ms 39676 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39504 KB n=5
2 Correct 7 ms 39680 KB n=100
3 Correct 8 ms 39504 KB n=100
4 Correct 8 ms 39640 KB n=100
5 Correct 7 ms 39504 KB n=100
6 Correct 7 ms 39504 KB n=100
7 Correct 7 ms 39504 KB n=100
8 Correct 7 ms 39648 KB n=100
9 Correct 7 ms 39516 KB n=100
10 Correct 8 ms 39504 KB n=100
11 Correct 6 ms 39504 KB n=100
12 Correct 6 ms 39504 KB n=100
13 Correct 6 ms 39504 KB n=100
14 Correct 6 ms 39504 KB n=100
15 Correct 6 ms 39504 KB n=100
16 Correct 6 ms 39504 KB n=100
17 Correct 6 ms 39504 KB n=100
18 Correct 6 ms 39672 KB n=100
19 Correct 8 ms 39504 KB n=100
20 Correct 6 ms 39504 KB n=100
21 Correct 7 ms 39816 KB n=100
22 Correct 6 ms 39504 KB n=100
23 Correct 6 ms 39504 KB n=100
24 Correct 6 ms 39672 KB n=100
25 Correct 6 ms 39504 KB n=100
26 Correct 6 ms 39504 KB n=12
27 Correct 7 ms 39676 KB n=100
28 Correct 7 ms 39772 KB n=500
29 Correct 7 ms 39772 KB n=500
30 Correct 7 ms 39760 KB n=500
31 Correct 7 ms 39760 KB n=500
32 Correct 7 ms 39760 KB n=500
33 Correct 7 ms 39928 KB n=500
34 Correct 6 ms 39760 KB n=500
35 Correct 7 ms 39772 KB n=500
36 Correct 10 ms 39760 KB n=500
37 Correct 8 ms 39760 KB n=500
38 Correct 8 ms 39760 KB n=500
39 Correct 8 ms 39760 KB n=500
40 Correct 7 ms 39760 KB n=500
41 Correct 8 ms 39760 KB n=500
42 Correct 7 ms 39820 KB n=500
43 Correct 7 ms 39760 KB n=500
44 Correct 11 ms 39760 KB n=500
45 Correct 7 ms 39760 KB n=500
46 Correct 8 ms 39760 KB n=500
47 Correct 7 ms 39760 KB n=500
48 Correct 7 ms 39760 KB n=500
49 Correct 7 ms 39760 KB n=500
50 Correct 7 ms 39640 KB n=500
51 Correct 8 ms 39760 KB n=500
52 Correct 7 ms 39760 KB n=500
53 Correct 8 ms 39760 KB n=500
54 Correct 8 ms 39928 KB n=500
55 Correct 7 ms 40016 KB n=278
56 Correct 6 ms 39760 KB n=500
57 Correct 9 ms 39760 KB n=500
58 Correct 7 ms 39760 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39504 KB n=5
2 Correct 7 ms 39680 KB n=100
3 Correct 8 ms 39504 KB n=100
4 Correct 8 ms 39640 KB n=100
5 Correct 7 ms 39504 KB n=100
6 Correct 7 ms 39504 KB n=100
7 Correct 7 ms 39504 KB n=100
8 Correct 7 ms 39648 KB n=100
9 Correct 7 ms 39516 KB n=100
10 Correct 8 ms 39504 KB n=100
11 Correct 6 ms 39504 KB n=100
12 Correct 6 ms 39504 KB n=100
13 Correct 6 ms 39504 KB n=100
14 Correct 6 ms 39504 KB n=100
15 Correct 6 ms 39504 KB n=100
16 Correct 6 ms 39504 KB n=100
17 Correct 6 ms 39504 KB n=100
18 Correct 6 ms 39672 KB n=100
19 Correct 8 ms 39504 KB n=100
20 Correct 6 ms 39504 KB n=100
21 Correct 7 ms 39816 KB n=100
22 Correct 6 ms 39504 KB n=100
23 Correct 6 ms 39504 KB n=100
24 Correct 6 ms 39672 KB n=100
25 Correct 6 ms 39504 KB n=100
26 Correct 6 ms 39504 KB n=12
27 Correct 7 ms 39676 KB n=100
28 Correct 7 ms 39772 KB n=500
29 Correct 7 ms 39772 KB n=500
30 Correct 7 ms 39760 KB n=500
31 Correct 7 ms 39760 KB n=500
32 Correct 7 ms 39760 KB n=500
33 Correct 7 ms 39928 KB n=500
34 Correct 6 ms 39760 KB n=500
35 Correct 7 ms 39772 KB n=500
36 Correct 10 ms 39760 KB n=500
37 Correct 8 ms 39760 KB n=500
38 Correct 8 ms 39760 KB n=500
39 Correct 8 ms 39760 KB n=500
40 Correct 7 ms 39760 KB n=500
41 Correct 8 ms 39760 KB n=500
42 Correct 7 ms 39820 KB n=500
43 Correct 7 ms 39760 KB n=500
44 Correct 11 ms 39760 KB n=500
45 Correct 7 ms 39760 KB n=500
46 Correct 8 ms 39760 KB n=500
47 Correct 7 ms 39760 KB n=500
48 Correct 7 ms 39760 KB n=500
49 Correct 7 ms 39760 KB n=500
50 Correct 7 ms 39640 KB n=500
51 Correct 8 ms 39760 KB n=500
52 Correct 7 ms 39760 KB n=500
53 Correct 8 ms 39760 KB n=500
54 Correct 8 ms 39928 KB n=500
55 Correct 7 ms 40016 KB n=278
56 Correct 6 ms 39760 KB n=500
57 Correct 9 ms 39760 KB n=500
58 Correct 7 ms 39760 KB n=500
59 Correct 10 ms 40288 KB n=2000
60 Correct 9 ms 40288 KB n=2000
61 Correct 10 ms 40168 KB n=2000
62 Correct 10 ms 40296 KB n=2000
63 Correct 8 ms 40284 KB n=2000
64 Correct 10 ms 40196 KB n=2000
65 Correct 10 ms 40284 KB n=2000
66 Correct 8 ms 40284 KB n=2000
67 Correct 9 ms 40440 KB n=2000
68 Correct 10 ms 40284 KB n=2000
69 Correct 9 ms 40272 KB n=2000
70 Correct 8 ms 40272 KB n=2000
71 Correct 8 ms 40272 KB n=2000
72 Correct 8 ms 40272 KB n=2000
73 Correct 8 ms 40272 KB n=2000
74 Correct 9 ms 40272 KB n=1844
75 Correct 10 ms 40272 KB n=2000
76 Correct 9 ms 40272 KB n=2000
77 Correct 10 ms 40272 KB n=2000
78 Correct 9 ms 40272 KB n=2000
79 Correct 9 ms 40272 KB n=2000
80 Correct 11 ms 40272 KB n=2000
81 Correct 10 ms 40272 KB n=2000
82 Correct 9 ms 40272 KB n=2000
83 Correct 11 ms 40272 KB n=2000
84 Correct 11 ms 40440 KB n=2000
85 Correct 9 ms 40272 KB n=2000
86 Correct 10 ms 40272 KB n=2000
87 Correct 10 ms 40272 KB n=2000
88 Correct 10 ms 40284 KB n=2000
89 Correct 9 ms 40272 KB n=2000
90 Correct 9 ms 40272 KB n=2000
91 Correct 9 ms 40272 KB n=2000

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39504 KB n=5
2 Correct 7 ms 39680 KB n=100
3 Correct 8 ms 39504 KB n=100
4 Correct 8 ms 39640 KB n=100
5 Correct 7 ms 39504 KB n=100
6 Correct 7 ms 39504 KB n=100
7 Correct 7 ms 39504 KB n=100
8 Correct 7 ms 39648 KB n=100
9 Correct 7 ms 39516 KB n=100
10 Correct 8 ms 39504 KB n=100
11 Correct 6 ms 39504 KB n=100
12 Correct 6 ms 39504 KB n=100
13 Correct 6 ms 39504 KB n=100
14 Correct 6 ms 39504 KB n=100
15 Correct 6 ms 39504 KB n=100
16 Correct 6 ms 39504 KB n=100
17 Correct 6 ms 39504 KB n=100
18 Correct 6 ms 39672 KB n=100
19 Correct 8 ms 39504 KB n=100
20 Correct 6 ms 39504 KB n=100
21 Correct 7 ms 39816 KB n=100
22 Correct 6 ms 39504 KB n=100
23 Correct 6 ms 39504 KB n=100
24 Correct 6 ms 39672 KB n=100
25 Correct 6 ms 39504 KB n=100
26 Correct 6 ms 39504 KB n=12
27 Correct 7 ms 39676 KB n=100
28 Correct 7 ms 39772 KB n=500
29 Correct 7 ms 39772 KB n=500
30 Correct 7 ms 39760 KB n=500
31 Correct 7 ms 39760 KB n=500
32 Correct 7 ms 39760 KB n=500
33 Correct 7 ms 39928 KB n=500
34 Correct 6 ms 39760 KB n=500
35 Correct 7 ms 39772 KB n=500
36 Correct 10 ms 39760 KB n=500
37 Correct 8 ms 39760 KB n=500
38 Correct 8 ms 39760 KB n=500
39 Correct 8 ms 39760 KB n=500
40 Correct 7 ms 39760 KB n=500
41 Correct 8 ms 39760 KB n=500
42 Correct 7 ms 39820 KB n=500
43 Correct 7 ms 39760 KB n=500
44 Correct 11 ms 39760 KB n=500
45 Correct 7 ms 39760 KB n=500
46 Correct 8 ms 39760 KB n=500
47 Correct 7 ms 39760 KB n=500
48 Correct 7 ms 39760 KB n=500
49 Correct 7 ms 39760 KB n=500
50 Correct 7 ms 39640 KB n=500
51 Correct 8 ms 39760 KB n=500
52 Correct 7 ms 39760 KB n=500
53 Correct 8 ms 39760 KB n=500
54 Correct 8 ms 39928 KB n=500
55 Correct 7 ms 40016 KB n=278
56 Correct 6 ms 39760 KB n=500
57 Correct 9 ms 39760 KB n=500
58 Correct 7 ms 39760 KB n=500
59 Correct 10 ms 40288 KB n=2000
60 Correct 9 ms 40288 KB n=2000
61 Correct 10 ms 40168 KB n=2000
62 Correct 10 ms 40296 KB n=2000
63 Correct 8 ms 40284 KB n=2000
64 Correct 10 ms 40196 KB n=2000
65 Correct 10 ms 40284 KB n=2000
66 Correct 8 ms 40284 KB n=2000
67 Correct 9 ms 40440 KB n=2000
68 Correct 10 ms 40284 KB n=2000
69 Correct 9 ms 40272 KB n=2000
70 Correct 8 ms 40272 KB n=2000
71 Correct 8 ms 40272 KB n=2000
72 Correct 8 ms 40272 KB n=2000
73 Correct 8 ms 40272 KB n=2000
74 Correct 9 ms 40272 KB n=1844
75 Correct 10 ms 40272 KB n=2000
76 Correct 9 ms 40272 KB n=2000
77 Correct 10 ms 40272 KB n=2000
78 Correct 9 ms 40272 KB n=2000
79 Correct 9 ms 40272 KB n=2000
80 Correct 11 ms 40272 KB n=2000
81 Correct 10 ms 40272 KB n=2000
82 Correct 9 ms 40272 KB n=2000
83 Correct 11 ms 40272 KB n=2000
84 Correct 11 ms 40440 KB n=2000
85 Correct 9 ms 40272 KB n=2000
86 Correct 10 ms 40272 KB n=2000
87 Correct 10 ms 40272 KB n=2000
88 Correct 10 ms 40284 KB n=2000
89 Correct 9 ms 40272 KB n=2000
90 Correct 9 ms 40272 KB n=2000
91 Correct 9 ms 40272 KB n=2000
92 Correct 556 ms 110348 KB n=200000
93 Correct 696 ms 113992 KB n=200000
94 Correct 494 ms 117120 KB n=200000
95 Correct 469 ms 111032 KB n=200000
96 Correct 453 ms 111032 KB n=200000
97 Correct 649 ms 113268 KB n=200000
98 Correct 535 ms 111288 KB n=200000
99 Correct 666 ms 109992 KB n=200000
100 Correct 575 ms 110268 KB n=200000
101 Correct 422 ms 117832 KB n=200000
102 Correct 329 ms 111488 KB n=200000
103 Correct 327 ms 111432 KB n=200000
104 Correct 348 ms 111356 KB n=200000
105 Correct 340 ms 111176 KB n=200000
106 Correct 354 ms 111176 KB n=200000
107 Correct 337 ms 111176 KB n=200000
108 Correct 509 ms 110152 KB n=200000
109 Correct 495 ms 110152 KB n=200000
110 Correct 488 ms 110152 KB n=200000
111 Correct 558 ms 110908 KB n=200000
112 Correct 485 ms 117216 KB n=200000
113 Correct 688 ms 113128 KB n=200000
114 Correct 467 ms 111032 KB n=200000
115 Correct 774 ms 111060 KB n=200000
116 Correct 546 ms 110896 KB n=200000
117 Correct 439 ms 117472 KB n=200000
118 Correct 835 ms 112196 KB n=200000
119 Correct 444 ms 110520 KB n=200000
120 Correct 337 ms 117512 KB n=200000
121 Correct 340 ms 117576 KB n=200000
122 Correct 392 ms 117912 KB n=200000
123 Correct 357 ms 110920 KB n=200000
124 Incorrect 101 ms 56648 KB Wrong range.
125 Halted 0 ms 0 KB -