oj.uz

Submission #58097

# Submission time Handle Problem Language Result Execution time Memory
58097 2018-07-16T19:45:56 Z Benq Birthday gift (IZhO18_treearray) C++14
100 / 100
 1801 ms 197940 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;

template<class T, int SZ> struct RMQ {
    T stor[SZ][32-__builtin_clz(SZ)];
    
    T comb(T a, T b) {
        return min(a,b);
    }
    
    void build(vector<T>& x) {
        F0R(i,sz(x)) stor[i][0] = x[i];
        FOR(j,1,32-__builtin_clz(SZ)) F0R(i,SZ-(1<<(j-1))) 
            stor[i][j] = comb(stor[i][j-1],
                        stor[i+(1<<(j-1))][j-1]);
    }
    
    T query(int l, int r) {
        int x = 31-__builtin_clz(r-l+1);
        return comb(stor[l][x],stor[r-(1<<x)+1][x]);
    }
};

template<int SZ> struct LCA {
    vi edges[SZ];
    RMQ<pi,2*SZ> r;
    vpi tmp;
    int depth[SZ], pos[SZ];
    
    int V, R = 1;
    
    void addEdge(int u, int v) {
        edges[u].pb(v), edges[v].pb(u);
    }
    
    void dfs(int u, int prev){
        pos[u] = sz(tmp); depth[u] = depth[prev]+1;
        tmp.pb({depth[u],u});
        for (int v: edges[u]) if (v != prev) {
            dfs(v, u);
            tmp.pb({depth[u],u});
        }
    }
    
    void construct() {
        dfs(R, 0);
        r.build(tmp);
    }
    
    int lca(int u, int v){
        u = pos[u], v = pos[v];
        if (u > v) swap(u,v);
        return r.query(u,v).s;
    }
    
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
};

LCA<MX> L;

int n,m,q,a[MX];
set<int> S1[MX], S2[MX];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    L.V = n;
    F0R(i,n-1) {
        int u,v; cin >> u >> v;
        L.addEdge(u,v);
    }
    L.construct();
    FOR(i,1,m+1) {
        cin >> a[i];
        S1[a[i]].insert(i);
        if (i > 1) S2[L.lca(a[i-1],a[i])].insert(i-1);
    }
    F0R(i,q) {
        int t; cin >> t;
        if (t == 1) {
            int pos, v; cin >> pos >> v;
            S1[a[pos]].erase(pos);
            if (pos > 1) S2[L.lca(a[pos-1],a[pos])].erase(pos-1);
            if (pos < m) S2[L.lca(a[pos],a[pos+1])].erase(pos);
            
            a[pos] = v;
            
            S1[a[pos]].insert({pos,pos});
            if (pos > 1) S2[L.lca(a[pos-1],a[pos])].insert(pos-1);
            if (pos < m) S2[L.lca(a[pos],a[pos+1])].insert(pos);
        } else {
            int l,r,v; cin >> l >> r >> v;
            auto it = S1[v].lb(l);
            if (it != S1[v].end() && *it <= r) cout << *it << " " << *it << "\n";
            else {
                it = S2[v].lb(l);
                if (it != S2[v].end() && *it < r) cout << *it << " " << (*it+1) << "\n";
                else cout << "-1 -1\n";
            }
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 83320 KB n=5
2 Correct 227 ms 83436 KB n=100
3 Correct 231 ms 83488 KB n=100
4 Correct 228 ms 83488 KB n=100
5 Correct 229 ms 83488 KB n=100
6 Correct 230 ms 83520 KB n=100
7 Correct 222 ms 83520 KB n=100
8 Correct 254 ms 83520 KB n=100
9 Correct 229 ms 83652 KB n=100
10 Correct 221 ms 83652 KB n=100
11 Correct 218 ms 83652 KB n=100
12 Correct 241 ms 83652 KB n=100
13 Correct 219 ms 83652 KB n=100
14 Correct 252 ms 83652 KB n=100
15 Correct 257 ms 83652 KB n=100
16 Correct 260 ms 83652 KB n=100
17 Correct 262 ms 83652 KB n=100
18 Correct 269 ms 83652 KB n=100
19 Correct 276 ms 83668 KB n=100
20 Correct 300 ms 83668 KB n=100
21 Correct 296 ms 83732 KB n=100
22 Correct 276 ms 83732 KB n=100
23 Correct 263 ms 83748 KB n=100
24 Correct 268 ms 83748 KB n=100
25 Correct 263 ms 83748 KB n=100
26 Correct 246 ms 83748 KB n=12
27 Correct 262 ms 83748 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 83320 KB n=5
2 Correct 227 ms 83436 KB n=100
3 Correct 231 ms 83488 KB n=100
4 Correct 228 ms 83488 KB n=100
5 Correct 229 ms 83488 KB n=100
6 Correct 230 ms 83520 KB n=100
7 Correct 222 ms 83520 KB n=100
8 Correct 254 ms 83520 KB n=100
9 Correct 229 ms 83652 KB n=100
10 Correct 221 ms 83652 KB n=100
11 Correct 218 ms 83652 KB n=100
12 Correct 241 ms 83652 KB n=100
13 Correct 219 ms 83652 KB n=100
14 Correct 252 ms 83652 KB n=100
15 Correct 257 ms 83652 KB n=100
16 Correct 260 ms 83652 KB n=100
17 Correct 262 ms 83652 KB n=100
18 Correct 269 ms 83652 KB n=100
19 Correct 276 ms 83668 KB n=100
20 Correct 300 ms 83668 KB n=100
21 Correct 296 ms 83732 KB n=100
22 Correct 276 ms 83732 KB n=100
23 Correct 263 ms 83748 KB n=100
24 Correct 268 ms 83748 KB n=100
25 Correct 263 ms 83748 KB n=100
26 Correct 246 ms 83748 KB n=12
27 Correct 262 ms 83748 KB n=100
28 Correct 268 ms 83748 KB n=500
29 Correct 302 ms 83748 KB n=500
30 Correct 264 ms 83748 KB n=500
31 Correct 265 ms 83748 KB n=500
32 Correct 280 ms 83788 KB n=500
33 Correct 273 ms 83788 KB n=500
34 Correct 281 ms 83788 KB n=500
35 Correct 302 ms 83788 KB n=500
36 Correct 286 ms 83788 KB n=500
37 Correct 288 ms 83788 KB n=500
38 Correct 261 ms 83788 KB n=500
39 Correct 294 ms 83788 KB n=500
40 Correct 269 ms 83788 KB n=500
41 Correct 260 ms 83788 KB n=500
42 Correct 259 ms 83788 KB n=500
43 Correct 272 ms 83788 KB n=500
44 Correct 266 ms 83788 KB n=500
45 Correct 279 ms 83788 KB n=500
46 Correct 278 ms 83788 KB n=500
47 Correct 272 ms 83788 KB n=500
48 Correct 270 ms 83788 KB n=500
49 Correct 272 ms 83788 KB n=500
50 Correct 278 ms 83788 KB n=500
51 Correct 277 ms 83788 KB n=500
52 Correct 284 ms 83788 KB n=500
53 Correct 279 ms 83788 KB n=500
54 Correct 265 ms 83920 KB n=500
55 Correct 270 ms 83920 KB n=278
56 Correct 268 ms 83920 KB n=500
57 Correct 292 ms 83920 KB n=500
58 Correct 274 ms 83920 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 83320 KB n=5
2 Correct 227 ms 83436 KB n=100
3 Correct 231 ms 83488 KB n=100
4 Correct 228 ms 83488 KB n=100
5 Correct 229 ms 83488 KB n=100
6 Correct 230 ms 83520 KB n=100
7 Correct 222 ms 83520 KB n=100
8 Correct 254 ms 83520 KB n=100
9 Correct 229 ms 83652 KB n=100
10 Correct 221 ms 83652 KB n=100
11 Correct 218 ms 83652 KB n=100
12 Correct 241 ms 83652 KB n=100
13 Correct 219 ms 83652 KB n=100
14 Correct 252 ms 83652 KB n=100
15 Correct 257 ms 83652 KB n=100
16 Correct 260 ms 83652 KB n=100
17 Correct 262 ms 83652 KB n=100
18 Correct 269 ms 83652 KB n=100
19 Correct 276 ms 83668 KB n=100
20 Correct 300 ms 83668 KB n=100
21 Correct 296 ms 83732 KB n=100
22 Correct 276 ms 83732 KB n=100
23 Correct 263 ms 83748 KB n=100
24 Correct 268 ms 83748 KB n=100
25 Correct 263 ms 83748 KB n=100
26 Correct 246 ms 83748 KB n=12
27 Correct 262 ms 83748 KB n=100
28 Correct 268 ms 83748 KB n=500
29 Correct 302 ms 83748 KB n=500
30 Correct 264 ms 83748 KB n=500
31 Correct 265 ms 83748 KB n=500
32 Correct 280 ms 83788 KB n=500
33 Correct 273 ms 83788 KB n=500
34 Correct 281 ms 83788 KB n=500
35 Correct 302 ms 83788 KB n=500
36 Correct 286 ms 83788 KB n=500
37 Correct 288 ms 83788 KB n=500
38 Correct 261 ms 83788 KB n=500
39 Correct 294 ms 83788 KB n=500
40 Correct 269 ms 83788 KB n=500
41 Correct 260 ms 83788 KB n=500
42 Correct 259 ms 83788 KB n=500
43 Correct 272 ms 83788 KB n=500
44 Correct 266 ms 83788 KB n=500
45 Correct 279 ms 83788 KB n=500
46 Correct 278 ms 83788 KB n=500
47 Correct 272 ms 83788 KB n=500
48 Correct 270 ms 83788 KB n=500
49 Correct 272 ms 83788 KB n=500
50 Correct 278 ms 83788 KB n=500
51 Correct 277 ms 83788 KB n=500
52 Correct 284 ms 83788 KB n=500
53 Correct 279 ms 83788 KB n=500
54 Correct 265 ms 83920 KB n=500
55 Correct 270 ms 83920 KB n=278
56 Correct 268 ms 83920 KB n=500
57 Correct 292 ms 83920 KB n=500
58 Correct 274 ms 83920 KB n=500
59 Correct 270 ms 83960 KB n=2000
60 Correct 277 ms 83972 KB n=2000
61 Correct 292 ms 83972 KB n=2000
62 Correct 292 ms 84000 KB n=2000
63 Correct 308 ms 84000 KB n=2000
64 Correct 276 ms 84032 KB n=2000
65 Correct 262 ms 84032 KB n=2000
66 Correct 270 ms 84116 KB n=2000
67 Correct 277 ms 84116 KB n=2000
68 Correct 276 ms 84116 KB n=2000
69 Correct 304 ms 84116 KB n=2000
70 Correct 288 ms 84116 KB n=2000
71 Correct 265 ms 84116 KB n=2000
72 Correct 269 ms 84116 KB n=2000
73 Correct 264 ms 84116 KB n=2000
74 Correct 294 ms 84116 KB n=1844
75 Correct 272 ms 84116 KB n=2000
76 Correct 270 ms 84116 KB n=2000
77 Correct 282 ms 84232 KB n=2000
78 Correct 298 ms 84232 KB n=2000
79 Correct 278 ms 84232 KB n=2000
80 Correct 285 ms 84232 KB n=2000
81 Correct 278 ms 84232 KB n=2000
82 Correct 282 ms 84232 KB n=2000
83 Correct 294 ms 84232 KB n=2000
84 Correct 294 ms 84232 KB n=2000
85 Correct 270 ms 84232 KB n=2000
86 Correct 300 ms 84232 KB n=2000
87 Correct 274 ms 84232 KB n=2000
88 Correct 268 ms 84232 KB n=2000
89 Correct 256 ms 84232 KB n=2000
90 Correct 261 ms 84232 KB n=2000
91 Correct 287 ms 84232 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 83320 KB n=5
2 Correct 227 ms 83436 KB n=100
3 Correct 231 ms 83488 KB n=100
4 Correct 228 ms 83488 KB n=100
5 Correct 229 ms 83488 KB n=100
6 Correct 230 ms 83520 KB n=100
7 Correct 222 ms 83520 KB n=100
8 Correct 254 ms 83520 KB n=100
9 Correct 229 ms 83652 KB n=100
10 Correct 221 ms 83652 KB n=100
11 Correct 218 ms 83652 KB n=100
12 Correct 241 ms 83652 KB n=100
13 Correct 219 ms 83652 KB n=100
14 Correct 252 ms 83652 KB n=100
15 Correct 257 ms 83652 KB n=100
16 Correct 260 ms 83652 KB n=100
17 Correct 262 ms 83652 KB n=100
18 Correct 269 ms 83652 KB n=100
19 Correct 276 ms 83668 KB n=100
20 Correct 300 ms 83668 KB n=100
21 Correct 296 ms 83732 KB n=100
22 Correct 276 ms 83732 KB n=100
23 Correct 263 ms 83748 KB n=100
24 Correct 268 ms 83748 KB n=100
25 Correct 263 ms 83748 KB n=100
26 Correct 246 ms 83748 KB n=12
27 Correct 262 ms 83748 KB n=100
28 Correct 268 ms 83748 KB n=500
29 Correct 302 ms 83748 KB n=500
30 Correct 264 ms 83748 KB n=500
31 Correct 265 ms 83748 KB n=500
32 Correct 280 ms 83788 KB n=500
33 Correct 273 ms 83788 KB n=500
34 Correct 281 ms 83788 KB n=500
35 Correct 302 ms 83788 KB n=500
36 Correct 286 ms 83788 KB n=500
37 Correct 288 ms 83788 KB n=500
38 Correct 261 ms 83788 KB n=500
39 Correct 294 ms 83788 KB n=500
40 Correct 269 ms 83788 KB n=500
41 Correct 260 ms 83788 KB n=500
42 Correct 259 ms 83788 KB n=500
43 Correct 272 ms 83788 KB n=500
44 Correct 266 ms 83788 KB n=500
45 Correct 279 ms 83788 KB n=500
46 Correct 278 ms 83788 KB n=500
47 Correct 272 ms 83788 KB n=500
48 Correct 270 ms 83788 KB n=500
49 Correct 272 ms 83788 KB n=500
50 Correct 278 ms 83788 KB n=500
51 Correct 277 ms 83788 KB n=500
52 Correct 284 ms 83788 KB n=500
53 Correct 279 ms 83788 KB n=500
54 Correct 265 ms 83920 KB n=500
55 Correct 270 ms 83920 KB n=278
56 Correct 268 ms 83920 KB n=500
57 Correct 292 ms 83920 KB n=500
58 Correct 274 ms 83920 KB n=500
59 Correct 270 ms 83960 KB n=2000
60 Correct 277 ms 83972 KB n=2000
61 Correct 292 ms 83972 KB n=2000
62 Correct 292 ms 84000 KB n=2000
63 Correct 308 ms 84000 KB n=2000
64 Correct 276 ms 84032 KB n=2000
65 Correct 262 ms 84032 KB n=2000
66 Correct 270 ms 84116 KB n=2000
67 Correct 277 ms 84116 KB n=2000
68 Correct 276 ms 84116 KB n=2000
69 Correct 304 ms 84116 KB n=2000
70 Correct 288 ms 84116 KB n=2000
71 Correct 265 ms 84116 KB n=2000
72 Correct 269 ms 84116 KB n=2000
73 Correct 264 ms 84116 KB n=2000
74 Correct 294 ms 84116 KB n=1844
75 Correct 272 ms 84116 KB n=2000
76 Correct 270 ms 84116 KB n=2000
77 Correct 282 ms 84232 KB n=2000
78 Correct 298 ms 84232 KB n=2000
79 Correct 278 ms 84232 KB n=2000
80 Correct 285 ms 84232 KB n=2000
81 Correct 278 ms 84232 KB n=2000
82 Correct 282 ms 84232 KB n=2000
83 Correct 294 ms 84232 KB n=2000
84 Correct 294 ms 84232 KB n=2000
85 Correct 270 ms 84232 KB n=2000
86 Correct 300 ms 84232 KB n=2000
87 Correct 274 ms 84232 KB n=2000
88 Correct 268 ms 84232 KB n=2000
89 Correct 256 ms 84232 KB n=2000
90 Correct 261 ms 84232 KB n=2000
91 Correct 287 ms 84232 KB n=2000
92 Correct 1595 ms 116148 KB n=200000
93 Correct 1480 ms 119320 KB n=200000
94 Correct 1437 ms 122264 KB n=200000
95 Correct 1593 ms 122264 KB n=200000
96 Correct 1457 ms 122264 KB n=200000
97 Correct 1436 ms 122264 KB n=200000
98 Correct 1504 ms 122264 KB n=200000
99 Correct 1732 ms 122264 KB n=200000
100 Correct 1600 ms 122264 KB n=200000
101 Correct 1448 ms 123544 KB n=200000
102 Correct 954 ms 123544 KB n=200000
103 Correct 967 ms 123544 KB n=200000
104 Correct 997 ms 123544 KB n=200000
105 Correct 1022 ms 123544 KB n=200000
106 Correct 963 ms 123544 KB n=200000
107 Correct 921 ms 123544 KB n=200000
108 Correct 1567 ms 123544 KB n=200000
109 Correct 1610 ms 123544 KB n=200000
110 Correct 1569 ms 123544 KB n=200000
111 Correct 1554 ms 123544 KB n=200000
112 Correct 1403 ms 125208 KB n=200000
113 Correct 1520 ms 129044 KB n=200000
114 Correct 1690 ms 132520 KB n=200000
115 Correct 1801 ms 140716 KB n=200000
116 Correct 1579 ms 146960 KB n=200000
117 Correct 1455 ms 161360 KB n=200000
118 Correct 1647 ms 164124 KB n=200000
119 Correct 1663 ms 169304 KB n=200000
120 Correct 1278 ms 183308 KB n=200000
121 Correct 1267 ms 190180 KB n=200000
122 Correct 1392 ms 197644 KB n=200000
123 Correct 922 ms 197940 KB n=200000
124 Correct 692 ms 197940 KB n=25264