oj.uz

Submission #154922

# Submission time Handle Problem Language Result Execution time Memory
154922 2019-09-25T13:16:34 Z leatherman Birthday gift (IZhO18_treearray) C++14
100 / 100
 1843 ms 178876 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define ll int
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
#define PB push_back
#define endl "\n"
#define y1 sfsdaf
#define pll pair<ll, ll>
using namespace std;
typedef double ld;
const ll N = 4e5 + 200;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
ll h[N],ft[N],n,d[N],m,Q,x,y,st[N];
pair<ll, ll> T[N][25];
vector<pair<ll, ll> > a;
vector<ll> v[N];
set<ll> s[N],pisos[N];
set<ll> :: iterator it;
void dfs(ll x,ll y)
{
    h[x] = h[y] + 1;
    T[a.size()][0] = {h[x], x};
    ft[x] = a.size();
    a.PB({h[x], x});
    for(auto to : v[x]) if(!h[to])
    {
        dfs(to, x);
        T[a.size()][0] = {h[x], x};
        a.PB({h[x], x});
    }
}
ll lca(ll a,ll b)
{
    ll l,r,k;
    l = ft[a];
    r = ft[b];
    if(l > r) swap(l, r);
    k = st[r - l + 1];
    return min(T[l][k], T[r - (1 << k) + 1][k]).se;
}
void ins(ll val,ll pos)
{
    s[val].insert(pos);
}
void ers(ll val,ll pos)
{
    if(!s[val].empty() && s[val].find(pos) != s[val].end()) s[val].erase(pos);
}
void build(ll m)
{
    for(int i = 1; i <= m; i++) ins(lca(d[i], d[i + 1]), i);
}
int main()
{
    ios_base::sync_with_stdio();cin.tie(0);cout.tie(0);
    cin>>n>>m>>Q;
    for(int i = 1; i < n; i++)
    {
        cin>>x>>y;
        v[x].PB(y);
        v[y].PB(x);
    }
    dfs(1, 1);
    for(int i = 1; i <= 2 * n; i++)
    {
        st[i] = st[i - 1];
        if(1 << (st[i] + 1) <= i) st[i]++;
    }
    for(int j = 1; j < 20; j++)
    {
        x = (1 << (j - 1));
        for(int i = 0; i + x < a.size(); i++) T[i][j] = min(T[i][j - 1], T[i + x][j - 1]);
    }
    for(int i = 1; i <= m; i++)
    {
        cin>>d[i];
        pisos[d[i]].insert(i);
    }
    m--;
    if(m) build(m);
    while(Q--)
    {
        ll t,pos,x,l,r,v;
        cin>>t;
        if(t == 1)
        {
            cin>>pos>>x;
            if(pos <= m) ers(lca(d[pos], d[pos + 1]), pos);
            if(pos - 1 > 0) ers(lca(d[pos - 1], d[pos]), pos - 1);


            pisos[d[pos]].erase(pos);
            d[pos] = x;
            pisos[d[pos]].insert(pos);

            if(pos <= m) ins(lca(d[pos], d[pos + 1]), pos);
            if(pos - 1 > 0) ins(lca(d[pos - 1], d[pos]), pos - 1);
        } else
        {
            cin>>l>>r>>v;
            if(!pisos[v].empty())
            {
                it = pisos[v].lower_bound(l);
                if(it != pisos[v].end()) x = *it;
                else x = 1e9;
                if(x <= r)
                {
                    cout<<x<<" "<<x<<endl;
                    continue;
                }
            }
            if(!s[v].empty())
            {
                it = s[v].lower_bound(l);
                if(it != s[v].end()) x = *it;
                else x = 1e9;
                if(x + 1 <= r)
                {
                    cout<<x<<" "<<x + 1<<endl;
                    continue;
                }
            }
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}
/*
1 1 1
1
2 1 1 1
*/

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:79:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i + x < a.size(); i++) T[i][j] = min(T[i][j - 1], T[i + x][j - 1]);
                        ~~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB n=5
2 Correct 46 ms 47372 KB n=100
3 Correct 47 ms 47352 KB n=100
4 Correct 46 ms 47480 KB n=100
5 Correct 46 ms 47352 KB n=100
6 Correct 47 ms 47432 KB n=100
7 Correct 46 ms 47352 KB n=100
8 Correct 47 ms 47352 KB n=100
9 Correct 46 ms 47352 KB n=100
10 Correct 47 ms 47328 KB n=100
11 Correct 47 ms 47480 KB n=100
12 Correct 47 ms 47420 KB n=100
13 Correct 47 ms 47356 KB n=100
14 Correct 47 ms 47328 KB n=100
15 Correct 46 ms 47316 KB n=100
16 Correct 46 ms 47352 KB n=100
17 Correct 47 ms 47352 KB n=100
18 Correct 47 ms 47480 KB n=100
19 Correct 53 ms 47480 KB n=100
20 Correct 47 ms 47396 KB n=100
21 Correct 54 ms 47480 KB n=100
22 Correct 46 ms 47452 KB n=100
23 Correct 47 ms 47352 KB n=100
24 Correct 47 ms 47480 KB n=100
25 Correct 47 ms 47456 KB n=100
26 Correct 47 ms 47480 KB n=12
27 Correct 47 ms 47480 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB n=5
2 Correct 46 ms 47372 KB n=100
3 Correct 47 ms 47352 KB n=100
4 Correct 46 ms 47480 KB n=100
5 Correct 46 ms 47352 KB n=100
6 Correct 47 ms 47432 KB n=100
7 Correct 46 ms 47352 KB n=100
8 Correct 47 ms 47352 KB n=100
9 Correct 46 ms 47352 KB n=100
10 Correct 47 ms 47328 KB n=100
11 Correct 47 ms 47480 KB n=100
12 Correct 47 ms 47420 KB n=100
13 Correct 47 ms 47356 KB n=100
14 Correct 47 ms 47328 KB n=100
15 Correct 46 ms 47316 KB n=100
16 Correct 46 ms 47352 KB n=100
17 Correct 47 ms 47352 KB n=100
18 Correct 47 ms 47480 KB n=100
19 Correct 53 ms 47480 KB n=100
20 Correct 47 ms 47396 KB n=100
21 Correct 54 ms 47480 KB n=100
22 Correct 46 ms 47452 KB n=100
23 Correct 47 ms 47352 KB n=100
24 Correct 47 ms 47480 KB n=100
25 Correct 47 ms 47456 KB n=100
26 Correct 47 ms 47480 KB n=12
27 Correct 47 ms 47480 KB n=100
28 Correct 49 ms 47580 KB n=500
29 Correct 48 ms 47736 KB n=500
30 Correct 49 ms 47608 KB n=500
31 Correct 48 ms 47608 KB n=500
32 Correct 48 ms 47608 KB n=500
33 Correct 48 ms 47608 KB n=500
34 Correct 48 ms 47616 KB n=500
35 Correct 55 ms 47736 KB n=500
36 Correct 48 ms 47608 KB n=500
37 Correct 47 ms 47608 KB n=500
38 Correct 48 ms 47608 KB n=500
39 Correct 48 ms 47592 KB n=500
40 Correct 48 ms 47608 KB n=500
41 Correct 48 ms 47608 KB n=500
42 Correct 48 ms 47608 KB n=500
43 Correct 49 ms 47608 KB n=500
44 Correct 48 ms 47716 KB n=500
45 Correct 48 ms 47608 KB n=500
46 Correct 48 ms 47608 KB n=500
47 Correct 49 ms 47608 KB n=500
48 Correct 49 ms 47736 KB n=500
49 Correct 48 ms 47612 KB n=500
50 Correct 47 ms 47608 KB n=500
51 Correct 48 ms 47608 KB n=500
52 Correct 48 ms 47608 KB n=500
53 Correct 48 ms 47608 KB n=500
54 Correct 49 ms 47736 KB n=500
55 Correct 48 ms 47480 KB n=278
56 Correct 48 ms 47608 KB n=500
57 Correct 51 ms 47708 KB n=500
58 Correct 48 ms 47576 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB n=5
2 Correct 46 ms 47372 KB n=100
3 Correct 47 ms 47352 KB n=100
4 Correct 46 ms 47480 KB n=100
5 Correct 46 ms 47352 KB n=100
6 Correct 47 ms 47432 KB n=100
7 Correct 46 ms 47352 KB n=100
8 Correct 47 ms 47352 KB n=100
9 Correct 46 ms 47352 KB n=100
10 Correct 47 ms 47328 KB n=100
11 Correct 47 ms 47480 KB n=100
12 Correct 47 ms 47420 KB n=100
13 Correct 47 ms 47356 KB n=100
14 Correct 47 ms 47328 KB n=100
15 Correct 46 ms 47316 KB n=100
16 Correct 46 ms 47352 KB n=100
17 Correct 47 ms 47352 KB n=100
18 Correct 47 ms 47480 KB n=100
19 Correct 53 ms 47480 KB n=100
20 Correct 47 ms 47396 KB n=100
21 Correct 54 ms 47480 KB n=100
22 Correct 46 ms 47452 KB n=100
23 Correct 47 ms 47352 KB n=100
24 Correct 47 ms 47480 KB n=100
25 Correct 47 ms 47456 KB n=100
26 Correct 47 ms 47480 KB n=12
27 Correct 47 ms 47480 KB n=100
28 Correct 49 ms 47580 KB n=500
29 Correct 48 ms 47736 KB n=500
30 Correct 49 ms 47608 KB n=500
31 Correct 48 ms 47608 KB n=500
32 Correct 48 ms 47608 KB n=500
33 Correct 48 ms 47608 KB n=500
34 Correct 48 ms 47616 KB n=500
35 Correct 55 ms 47736 KB n=500
36 Correct 48 ms 47608 KB n=500
37 Correct 47 ms 47608 KB n=500
38 Correct 48 ms 47608 KB n=500
39 Correct 48 ms 47592 KB n=500
40 Correct 48 ms 47608 KB n=500
41 Correct 48 ms 47608 KB n=500
42 Correct 48 ms 47608 KB n=500
43 Correct 49 ms 47608 KB n=500
44 Correct 48 ms 47716 KB n=500
45 Correct 48 ms 47608 KB n=500
46 Correct 48 ms 47608 KB n=500
47 Correct 49 ms 47608 KB n=500
48 Correct 49 ms 47736 KB n=500
49 Correct 48 ms 47612 KB n=500
50 Correct 47 ms 47608 KB n=500
51 Correct 48 ms 47608 KB n=500
52 Correct 48 ms 47608 KB n=500
53 Correct 48 ms 47608 KB n=500
54 Correct 49 ms 47736 KB n=500
55 Correct 48 ms 47480 KB n=278
56 Correct 48 ms 47608 KB n=500
57 Correct 51 ms 47708 KB n=500
58 Correct 48 ms 47576 KB n=500
59 Correct 55 ms 48528 KB n=2000
60 Correct 54 ms 48572 KB n=2000
61 Correct 55 ms 48632 KB n=2000
62 Correct 55 ms 48504 KB n=2000
63 Correct 54 ms 48476 KB n=2000
64 Correct 55 ms 48504 KB n=2000
65 Correct 55 ms 48476 KB n=2000
66 Correct 55 ms 48552 KB n=2000
67 Correct 55 ms 48604 KB n=2000
68 Correct 55 ms 48504 KB n=2000
69 Correct 54 ms 48504 KB n=2000
70 Correct 54 ms 48496 KB n=2000
71 Correct 54 ms 48588 KB n=2000
72 Correct 54 ms 48460 KB n=2000
73 Correct 53 ms 48504 KB n=2000
74 Correct 54 ms 48504 KB n=1844
75 Correct 54 ms 48504 KB n=2000
76 Correct 55 ms 48508 KB n=2000
77 Correct 55 ms 48476 KB n=2000
78 Correct 55 ms 48632 KB n=2000
79 Correct 53 ms 48476 KB n=2000
80 Correct 54 ms 48632 KB n=2000
81 Correct 54 ms 48504 KB n=2000
82 Correct 54 ms 48508 KB n=2000
83 Correct 54 ms 48632 KB n=2000
84 Correct 55 ms 48504 KB n=2000
85 Correct 55 ms 48504 KB n=2000
86 Correct 54 ms 48504 KB n=2000
87 Correct 55 ms 48504 KB n=2000
88 Correct 54 ms 48632 KB n=2000
89 Correct 53 ms 48620 KB n=2000
90 Correct 55 ms 48632 KB n=2000
91 Correct 53 ms 48536 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB n=5
2 Correct 46 ms 47372 KB n=100
3 Correct 47 ms 47352 KB n=100
4 Correct 46 ms 47480 KB n=100
5 Correct 46 ms 47352 KB n=100
6 Correct 47 ms 47432 KB n=100
7 Correct 46 ms 47352 KB n=100
8 Correct 47 ms 47352 KB n=100
9 Correct 46 ms 47352 KB n=100
10 Correct 47 ms 47328 KB n=100
11 Correct 47 ms 47480 KB n=100
12 Correct 47 ms 47420 KB n=100
13 Correct 47 ms 47356 KB n=100
14 Correct 47 ms 47328 KB n=100
15 Correct 46 ms 47316 KB n=100
16 Correct 46 ms 47352 KB n=100
17 Correct 47 ms 47352 KB n=100
18 Correct 47 ms 47480 KB n=100
19 Correct 53 ms 47480 KB n=100
20 Correct 47 ms 47396 KB n=100
21 Correct 54 ms 47480 KB n=100
22 Correct 46 ms 47452 KB n=100
23 Correct 47 ms 47352 KB n=100
24 Correct 47 ms 47480 KB n=100
25 Correct 47 ms 47456 KB n=100
26 Correct 47 ms 47480 KB n=12
27 Correct 47 ms 47480 KB n=100
28 Correct 49 ms 47580 KB n=500
29 Correct 48 ms 47736 KB n=500
30 Correct 49 ms 47608 KB n=500
31 Correct 48 ms 47608 KB n=500
32 Correct 48 ms 47608 KB n=500
33 Correct 48 ms 47608 KB n=500
34 Correct 48 ms 47616 KB n=500
35 Correct 55 ms 47736 KB n=500
36 Correct 48 ms 47608 KB n=500
37 Correct 47 ms 47608 KB n=500
38 Correct 48 ms 47608 KB n=500
39 Correct 48 ms 47592 KB n=500
40 Correct 48 ms 47608 KB n=500
41 Correct 48 ms 47608 KB n=500
42 Correct 48 ms 47608 KB n=500
43 Correct 49 ms 47608 KB n=500
44 Correct 48 ms 47716 KB n=500
45 Correct 48 ms 47608 KB n=500
46 Correct 48 ms 47608 KB n=500
47 Correct 49 ms 47608 KB n=500
48 Correct 49 ms 47736 KB n=500
49 Correct 48 ms 47612 KB n=500
50 Correct 47 ms 47608 KB n=500
51 Correct 48 ms 47608 KB n=500
52 Correct 48 ms 47608 KB n=500
53 Correct 48 ms 47608 KB n=500
54 Correct 49 ms 47736 KB n=500
55 Correct 48 ms 47480 KB n=278
56 Correct 48 ms 47608 KB n=500
57 Correct 51 ms 47708 KB n=500
58 Correct 48 ms 47576 KB n=500
59 Correct 55 ms 48528 KB n=2000
60 Correct 54 ms 48572 KB n=2000
61 Correct 55 ms 48632 KB n=2000
62 Correct 55 ms 48504 KB n=2000
63 Correct 54 ms 48476 KB n=2000
64 Correct 55 ms 48504 KB n=2000
65 Correct 55 ms 48476 KB n=2000
66 Correct 55 ms 48552 KB n=2000
67 Correct 55 ms 48604 KB n=2000
68 Correct 55 ms 48504 KB n=2000
69 Correct 54 ms 48504 KB n=2000
70 Correct 54 ms 48496 KB n=2000
71 Correct 54 ms 48588 KB n=2000
72 Correct 54 ms 48460 KB n=2000
73 Correct 53 ms 48504 KB n=2000
74 Correct 54 ms 48504 KB n=1844
75 Correct 54 ms 48504 KB n=2000
76 Correct 55 ms 48508 KB n=2000
77 Correct 55 ms 48476 KB n=2000
78 Correct 55 ms 48632 KB n=2000
79 Correct 53 ms 48476 KB n=2000
80 Correct 54 ms 48632 KB n=2000
81 Correct 54 ms 48504 KB n=2000
82 Correct 54 ms 48508 KB n=2000
83 Correct 54 ms 48632 KB n=2000
84 Correct 55 ms 48504 KB n=2000
85 Correct 55 ms 48504 KB n=2000
86 Correct 54 ms 48504 KB n=2000
87 Correct 55 ms 48504 KB n=2000
88 Correct 54 ms 48632 KB n=2000
89 Correct 53 ms 48620 KB n=2000
90 Correct 55 ms 48632 KB n=2000
91 Correct 53 ms 48536 KB n=2000
92 Correct 1645 ms 166044 KB n=200000
93 Correct 1758 ms 172468 KB n=200000
94 Correct 1597 ms 176980 KB n=200000
95 Correct 1618 ms 165996 KB n=200000
96 Correct 1557 ms 166276 KB n=200000
97 Correct 1687 ms 171580 KB n=200000
98 Correct 1601 ms 166060 KB n=200000
99 Correct 1798 ms 166284 KB n=200000
100 Correct 1600 ms 166272 KB n=200000
101 Correct 1557 ms 178876 KB n=200000
102 Correct 1182 ms 167272 KB n=200000
103 Correct 1185 ms 167488 KB n=200000
104 Correct 1223 ms 167288 KB n=200000
105 Correct 1258 ms 167852 KB n=200000
106 Correct 1241 ms 167724 KB n=200000
107 Correct 1243 ms 167584 KB n=200000
108 Correct 1695 ms 166192 KB n=200000
109 Correct 1668 ms 166084 KB n=200000
110 Correct 1729 ms 166260 KB n=200000
111 Correct 1601 ms 165564 KB n=200000
112 Correct 1575 ms 177544 KB n=200000
113 Correct 1648 ms 171384 KB n=200000
114 Correct 1635 ms 165764 KB n=200000
115 Correct 1843 ms 168660 KB n=200000
116 Correct 1581 ms 166372 KB n=200000
117 Correct 1588 ms 177988 KB n=200000
118 Correct 1622 ms 170164 KB n=200000
119 Correct 1576 ms 166192 KB n=200000
120 Correct 1459 ms 177764 KB n=200000
121 Correct 1458 ms 177968 KB n=200000
122 Correct 1440 ms 178124 KB n=200000
123 Correct 1227 ms 167464 KB n=200000
124 Correct 407 ms 71256 KB n=25264