oj.uz

Submission #58095

# Submission time Handle Problem Language Result Execution time Memory
58095 2018-07-16T19:39:07 Z Benq Birthday gift (IZhO18_treearray) C++14
56 / 100
 1777 ms 262360 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<pi> S[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];
        S[a[i]].insert({i,i});
        if (i > 1) S[L.lca(a[i-1],a[i])].insert({i-1,i});
    }
    F0R(i,q) {
        int t; cin >> t;
        if (t == 1) {
            int pos, v; cin >> pos >> v;
            S[a[pos]].erase({pos,pos});
            if (pos > 1) S[L.lca(a[pos-1],a[pos])].erase({pos-1,pos});
            if (pos < m) S[L.lca(a[pos],a[pos+1])].erase({pos,pos+1});
            
            a[pos] = v;
            
            S[a[pos]].insert({pos,pos});
            if (pos > 1) S[L.lca(a[pos-1],a[pos])].insert({pos-1,pos});
            if (pos < m) S[L.lca(a[pos],a[pos+1])].insert({pos,pos+1});
        } else {
            int l,r,v; cin >> l >> r >> v;
            auto it = S[v].lb({l,0});
            if (it != S[v].end() && it->s <= r) cout << it->f << " " << it->s << "\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 252 ms 74108 KB n=5
2 Correct 244 ms 74244 KB n=100
3 Correct 278 ms 74384 KB n=100
4 Correct 246 ms 74384 KB n=100
5 Correct 246 ms 74384 KB n=100
6 Correct 249 ms 74456 KB n=100
7 Correct 261 ms 74456 KB n=100
8 Correct 260 ms 74456 KB n=100
9 Correct 262 ms 74480 KB n=100
10 Correct 261 ms 74480 KB n=100
11 Correct 293 ms 74480 KB n=100
12 Correct 268 ms 74544 KB n=100
13 Correct 261 ms 74620 KB n=100
14 Correct 267 ms 74620 KB n=100
15 Correct 273 ms 74620 KB n=100
16 Correct 265 ms 74620 KB n=100
17 Correct 285 ms 74620 KB n=100
18 Correct 278 ms 74620 KB n=100
19 Correct 268 ms 74620 KB n=100
20 Correct 259 ms 74620 KB n=100
21 Correct 256 ms 74620 KB n=100
22 Correct 247 ms 74620 KB n=100
23 Correct 263 ms 74620 KB n=100
24 Correct 270 ms 74620 KB n=100
25 Correct 265 ms 74620 KB n=100
26 Correct 246 ms 74620 KB n=12
27 Correct 278 ms 74620 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 74108 KB n=5
2 Correct 244 ms 74244 KB n=100
3 Correct 278 ms 74384 KB n=100
4 Correct 246 ms 74384 KB n=100
5 Correct 246 ms 74384 KB n=100
6 Correct 249 ms 74456 KB n=100
7 Correct 261 ms 74456 KB n=100
8 Correct 260 ms 74456 KB n=100
9 Correct 262 ms 74480 KB n=100
10 Correct 261 ms 74480 KB n=100
11 Correct 293 ms 74480 KB n=100
12 Correct 268 ms 74544 KB n=100
13 Correct 261 ms 74620 KB n=100
14 Correct 267 ms 74620 KB n=100
15 Correct 273 ms 74620 KB n=100
16 Correct 265 ms 74620 KB n=100
17 Correct 285 ms 74620 KB n=100
18 Correct 278 ms 74620 KB n=100
19 Correct 268 ms 74620 KB n=100
20 Correct 259 ms 74620 KB n=100
21 Correct 256 ms 74620 KB n=100
22 Correct 247 ms 74620 KB n=100
23 Correct 263 ms 74620 KB n=100
24 Correct 270 ms 74620 KB n=100
25 Correct 265 ms 74620 KB n=100
26 Correct 246 ms 74620 KB n=12
27 Correct 278 ms 74620 KB n=100
28 Correct 254 ms 74644 KB n=500
29 Correct 258 ms 74644 KB n=500
30 Correct 269 ms 74668 KB n=500
31 Correct 294 ms 74700 KB n=500
32 Correct 278 ms 74700 KB n=500
33 Correct 276 ms 74748 KB n=500
34 Correct 258 ms 74748 KB n=500
35 Correct 270 ms 74756 KB n=500
36 Correct 240 ms 74756 KB n=500
37 Correct 280 ms 74800 KB n=500
38 Correct 253 ms 74808 KB n=500
39 Correct 244 ms 74880 KB n=500
40 Correct 239 ms 74896 KB n=500
41 Correct 271 ms 74912 KB n=500
42 Correct 241 ms 74912 KB n=500
43 Correct 257 ms 74912 KB n=500
44 Correct 251 ms 74952 KB n=500
45 Correct 246 ms 75020 KB n=500
46 Correct 241 ms 75048 KB n=500
47 Correct 242 ms 75048 KB n=500
48 Correct 249 ms 75048 KB n=500
49 Correct 263 ms 75056 KB n=500
50 Correct 248 ms 75056 KB n=500
51 Correct 241 ms 75084 KB n=500
52 Correct 255 ms 75100 KB n=500
53 Correct 253 ms 75100 KB n=500
54 Correct 242 ms 75132 KB n=500
55 Correct 236 ms 75272 KB n=278
56 Correct 277 ms 75272 KB n=500
57 Correct 244 ms 75272 KB n=500
58 Correct 268 ms 75272 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 74108 KB n=5
2 Correct 244 ms 74244 KB n=100
3 Correct 278 ms 74384 KB n=100
4 Correct 246 ms 74384 KB n=100
5 Correct 246 ms 74384 KB n=100
6 Correct 249 ms 74456 KB n=100
7 Correct 261 ms 74456 KB n=100
8 Correct 260 ms 74456 KB n=100
9 Correct 262 ms 74480 KB n=100
10 Correct 261 ms 74480 KB n=100
11 Correct 293 ms 74480 KB n=100
12 Correct 268 ms 74544 KB n=100
13 Correct 261 ms 74620 KB n=100
14 Correct 267 ms 74620 KB n=100
15 Correct 273 ms 74620 KB n=100
16 Correct 265 ms 74620 KB n=100
17 Correct 285 ms 74620 KB n=100
18 Correct 278 ms 74620 KB n=100
19 Correct 268 ms 74620 KB n=100
20 Correct 259 ms 74620 KB n=100
21 Correct 256 ms 74620 KB n=100
22 Correct 247 ms 74620 KB n=100
23 Correct 263 ms 74620 KB n=100
24 Correct 270 ms 74620 KB n=100
25 Correct 265 ms 74620 KB n=100
26 Correct 246 ms 74620 KB n=12
27 Correct 278 ms 74620 KB n=100
28 Correct 254 ms 74644 KB n=500
29 Correct 258 ms 74644 KB n=500
30 Correct 269 ms 74668 KB n=500
31 Correct 294 ms 74700 KB n=500
32 Correct 278 ms 74700 KB n=500
33 Correct 276 ms 74748 KB n=500
34 Correct 258 ms 74748 KB n=500
35 Correct 270 ms 74756 KB n=500
36 Correct 240 ms 74756 KB n=500
37 Correct 280 ms 74800 KB n=500
38 Correct 253 ms 74808 KB n=500
39 Correct 244 ms 74880 KB n=500
40 Correct 239 ms 74896 KB n=500
41 Correct 271 ms 74912 KB n=500
42 Correct 241 ms 74912 KB n=500
43 Correct 257 ms 74912 KB n=500
44 Correct 251 ms 74952 KB n=500
45 Correct 246 ms 75020 KB n=500
46 Correct 241 ms 75048 KB n=500
47 Correct 242 ms 75048 KB n=500
48 Correct 249 ms 75048 KB n=500
49 Correct 263 ms 75056 KB n=500
50 Correct 248 ms 75056 KB n=500
51 Correct 241 ms 75084 KB n=500
52 Correct 255 ms 75100 KB n=500
53 Correct 253 ms 75100 KB n=500
54 Correct 242 ms 75132 KB n=500
55 Correct 236 ms 75272 KB n=278
56 Correct 277 ms 75272 KB n=500
57 Correct 244 ms 75272 KB n=500
58 Correct 268 ms 75272 KB n=500
59 Correct 261 ms 75392 KB n=2000
60 Correct 256 ms 75628 KB n=2000
61 Correct 257 ms 75628 KB n=2000
62 Correct 251 ms 75628 KB n=2000
63 Correct 261 ms 75672 KB n=2000
64 Correct 249 ms 75760 KB n=2000
65 Correct 253 ms 75776 KB n=2000
66 Correct 257 ms 75876 KB n=2000
67 Correct 246 ms 75876 KB n=2000
68 Correct 270 ms 75940 KB n=2000
69 Correct 240 ms 75996 KB n=2000
70 Correct 251 ms 76108 KB n=2000
71 Correct 247 ms 76108 KB n=2000
72 Correct 244 ms 76152 KB n=2000
73 Correct 269 ms 76152 KB n=2000
74 Correct 250 ms 76312 KB n=1844
75 Correct 256 ms 76312 KB n=2000
76 Correct 241 ms 76364 KB n=2000
77 Correct 254 ms 76372 KB n=2000
78 Correct 252 ms 76372 KB n=2000
79 Correct 246 ms 76396 KB n=2000
80 Correct 244 ms 76576 KB n=2000
81 Correct 242 ms 76576 KB n=2000
82 Correct 237 ms 76684 KB n=2000
83 Correct 251 ms 76860 KB n=2000
84 Correct 245 ms 76860 KB n=2000
85 Correct 240 ms 76860 KB n=2000
86 Correct 259 ms 76896 KB n=2000
87 Correct 247 ms 76896 KB n=2000
88 Correct 252 ms 77036 KB n=2000
89 Correct 255 ms 77144 KB n=2000
90 Correct 241 ms 77260 KB n=2000
91 Correct 247 ms 77260 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 74108 KB n=5
2 Correct 244 ms 74244 KB n=100
3 Correct 278 ms 74384 KB n=100
4 Correct 246 ms 74384 KB n=100
5 Correct 246 ms 74384 KB n=100
6 Correct 249 ms 74456 KB n=100
7 Correct 261 ms 74456 KB n=100
8 Correct 260 ms 74456 KB n=100
9 Correct 262 ms 74480 KB n=100
10 Correct 261 ms 74480 KB n=100
11 Correct 293 ms 74480 KB n=100
12 Correct 268 ms 74544 KB n=100
13 Correct 261 ms 74620 KB n=100
14 Correct 267 ms 74620 KB n=100
15 Correct 273 ms 74620 KB n=100
16 Correct 265 ms 74620 KB n=100
17 Correct 285 ms 74620 KB n=100
18 Correct 278 ms 74620 KB n=100
19 Correct 268 ms 74620 KB n=100
20 Correct 259 ms 74620 KB n=100
21 Correct 256 ms 74620 KB n=100
22 Correct 247 ms 74620 KB n=100
23 Correct 263 ms 74620 KB n=100
24 Correct 270 ms 74620 KB n=100
25 Correct 265 ms 74620 KB n=100
26 Correct 246 ms 74620 KB n=12
27 Correct 278 ms 74620 KB n=100
28 Correct 254 ms 74644 KB n=500
29 Correct 258 ms 74644 KB n=500
30 Correct 269 ms 74668 KB n=500
31 Correct 294 ms 74700 KB n=500
32 Correct 278 ms 74700 KB n=500
33 Correct 276 ms 74748 KB n=500
34 Correct 258 ms 74748 KB n=500
35 Correct 270 ms 74756 KB n=500
36 Correct 240 ms 74756 KB n=500
37 Correct 280 ms 74800 KB n=500
38 Correct 253 ms 74808 KB n=500
39 Correct 244 ms 74880 KB n=500
40 Correct 239 ms 74896 KB n=500
41 Correct 271 ms 74912 KB n=500
42 Correct 241 ms 74912 KB n=500
43 Correct 257 ms 74912 KB n=500
44 Correct 251 ms 74952 KB n=500
45 Correct 246 ms 75020 KB n=500
46 Correct 241 ms 75048 KB n=500
47 Correct 242 ms 75048 KB n=500
48 Correct 249 ms 75048 KB n=500
49 Correct 263 ms 75056 KB n=500
50 Correct 248 ms 75056 KB n=500
51 Correct 241 ms 75084 KB n=500
52 Correct 255 ms 75100 KB n=500
53 Correct 253 ms 75100 KB n=500
54 Correct 242 ms 75132 KB n=500
55 Correct 236 ms 75272 KB n=278
56 Correct 277 ms 75272 KB n=500
57 Correct 244 ms 75272 KB n=500
58 Correct 268 ms 75272 KB n=500
59 Correct 261 ms 75392 KB n=2000
60 Correct 256 ms 75628 KB n=2000
61 Correct 257 ms 75628 KB n=2000
62 Correct 251 ms 75628 KB n=2000
63 Correct 261 ms 75672 KB n=2000
64 Correct 249 ms 75760 KB n=2000
65 Correct 253 ms 75776 KB n=2000
66 Correct 257 ms 75876 KB n=2000
67 Correct 246 ms 75876 KB n=2000
68 Correct 270 ms 75940 KB n=2000
69 Correct 240 ms 75996 KB n=2000
70 Correct 251 ms 76108 KB n=2000
71 Correct 247 ms 76108 KB n=2000
72 Correct 244 ms 76152 KB n=2000
73 Correct 269 ms 76152 KB n=2000
74 Correct 250 ms 76312 KB n=1844
75 Correct 256 ms 76312 KB n=2000
76 Correct 241 ms 76364 KB n=2000
77 Correct 254 ms 76372 KB n=2000
78 Correct 252 ms 76372 KB n=2000
79 Correct 246 ms 76396 KB n=2000
80 Correct 244 ms 76576 KB n=2000
81 Correct 242 ms 76576 KB n=2000
82 Correct 237 ms 76684 KB n=2000
83 Correct 251 ms 76860 KB n=2000
84 Correct 245 ms 76860 KB n=2000
85 Correct 240 ms 76860 KB n=2000
86 Correct 259 ms 76896 KB n=2000
87 Correct 247 ms 76896 KB n=2000
88 Correct 252 ms 77036 KB n=2000
89 Correct 255 ms 77144 KB n=2000
90 Correct 241 ms 77260 KB n=2000
91 Correct 247 ms 77260 KB n=2000
92 Correct 1516 ms 115860 KB n=200000
93 Correct 1324 ms 126708 KB n=200000
94 Correct 1256 ms 137324 KB n=200000
95 Correct 1548 ms 137624 KB n=200000
96 Correct 1591 ms 144000 KB n=200000
97 Correct 1387 ms 154220 KB n=200000
98 Correct 1777 ms 158100 KB n=200000
99 Correct 1744 ms 165016 KB n=200000
100 Correct 1655 ms 171880 KB n=200000
101 Correct 1254 ms 186684 KB n=200000
102 Correct 877 ms 187240 KB n=200000
103 Correct 916 ms 193864 KB n=200000
104 Correct 920 ms 200432 KB n=200000
105 Correct 913 ms 207752 KB n=200000
106 Correct 926 ms 214984 KB n=200000
107 Correct 964 ms 222472 KB n=200000
108 Correct 1225 ms 228236 KB n=200000
109 Correct 1180 ms 235204 KB n=200000
110 Correct 1171 ms 242024 KB n=200000
111 Correct 1312 ms 248300 KB n=200000
112 Runtime error 1067 ms 262360 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
113 Halted 0 ms 0 KB -