Submission #40438

#TimeUsernameProblemLanguageResultExecution timeMemory
40438szawinisBirthday gift (IZhO18_treearray)C++14
56 / 100
4046 ms262144 KiB
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <map> #include <set> using namespace std; const int N = 1 << 18; int n, m, q, a[N]; vector<int> g[N]; set<int> pos[N]; int d[N]; vector<int> anc[N]; void dfs(int u, int p) { for(int v: g[u]) if(v != p) { d[v] = d[u] + 1; anc[v].push_back(u); for(int j = 0; 1 << j+1 <= d[v]; j++) anc[v].push_back(anc[anc[v][j]][j]); dfs(v, u); } } int lca(int u, int v) { if(d[v] > d[u]) swap(u, v); if(d[u] > d[v]) { for(int j = 0; 1 << j <= d[u] - d[v]; j++) if(d[u] - d[v] >> j & 1) u = anc[u][j]; } if(u == v) return u; for(int j = 18; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j]) u = anc[u][j], v = anc[v][j]; return anc[u][0]; } map<int, set<int> > t[2*N]; void update(int i, int nw, int rm, int idx) { i += N; t[i][rm].erase(idx); t[i][nw].insert(idx); i >>= 1; while(i >= 1) { t[i][rm].erase(idx); t[i][nw].insert(idx); i >>= 1; } } int query(int l, int r, int v) { int res = -1; for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) { if(!t[l][v].empty()) res = *t[l][v].begin(); ++l; } if(r & 1) { --r; if(!t[r][v].empty()) res = *t[r][v].begin(); } } return res; } int main() { scanf("%d %d %d", &n, &m, &q); for(int i = 1, u, v; i < n; i++) { scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); for(int i = 1; i <= m; i++) { scanf("%d", a+i); pos[a[i]].insert(i); if(i > 1) t[N+i-1][lca(a[i-1], a[i])].insert(i-1); } for(int i = N-1; i >= 1; i--) { t[i].insert(t[i<<1].begin(), t[i<<1].end()); for(auto elem: t[i<<1|1]) { for(int v: elem.second) t[i][elem.first].insert(v); } } for(int z = 0, tp, l, r, v, i; z < q; z++) { scanf("%d", &tp); if(tp == 1) { scanf("%d %d", &i, &v); if(i < m) update(i, lca(v, a[i+1]), lca(a[i], a[i+1]), i); if(i > 1) update(i-1, lca(a[i-1], v), lca(a[i-1], a[i]), i-1); pos[a[i]].erase(i); a[i] = v; pos[a[i]].insert(i); } else { scanf("%d %d %d", &l, &r, &v); int res = query(l, r-1, v); if(res == -1) { auto it = pos[v].lower_bound(l); if(it == pos[v].end() || *it > r) printf("-1 -1\n"); else printf("%d %d\n", *it, *it); } else printf("%d %d\n", res, res+1); } } }

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:20:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(int j = 0; 1 << j+1 <= d[v]; j++)
                        ^
treearray.cpp: In function 'int lca(int, int)':
treearray.cpp:29:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    if(d[u] - d[v] >> j & 1) u = anc[u][j];
            ^
treearray.cpp:33:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j < anc[u].size() && anc[u][j] != anc[v][j])
        ^
treearray.cpp: In function 'int main()':
treearray.cpp:65:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
                               ^
treearray.cpp:67:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
                         ^
treearray.cpp:73:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
                   ^
treearray.cpp:85:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
                   ^
treearray.cpp:87:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &i, &v);
                          ^
treearray.cpp:94:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &l, &r, &v);
                                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...