fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define PI pair<int,int>
  4. #define MP make_pair
  5. #define PB push_back
  6. #define FI first
  7. #define SE second
  8. #define ll long long
  9. #define ALL(DATAST) DATAST.begin(), DATAST.end()
  10. #define SFD(d) scanf("%d",&d)
  11. #define SFLD(d) scanf("%lld",&d)
  12. #define FOR(i,a,b) for(int i=(a); i<(b); i++)
  13. #define FORL(i,a,b) for(ll i=(a); i<(b); i++)
  14. #define DBG cout<<"here"<<endl
  15. #define MOD 1000000007
  16. #define SIZE 111111
  17. #define MEM 35000
  18.  
  19. // PERSISTENT SEGTREE
  20.  
  21. struct node
  22. {
  23.     int val;
  24.     node *l;
  25.     node *r;
  26.     node()
  27.     {
  28.         val = 0;
  29.         l = r = NULL;
  30.     }
  31. };
  32.  
  33. void build(int s, int e, node *nd)
  34. {
  35.     if (s == e)
  36.     {
  37.         return;
  38.     }
  39.     int m = (s + e) / 2;
  40.     nd->l = new node();
  41.     nd->r = new node();
  42.     build(s, m, nd->l);
  43.     build(m + 1, e, nd->r);
  44. }
  45.  
  46. vector<int>adj[SIZE];
  47. int dep[SIZE];
  48. int par[25][SIZE];
  49. int n;
  50. int wt[SIZE];
  51. int temp[SIZE];
  52. node *vrsn[SIZE];
  53. int comp[SIZE];
  54. int k;
  55. int rm[SIZE];
  56.  
  57. void update(node *prev, node *cur, int s, int e, int i, int v)
  58. {
  59.     if (s > i || e < i)
  60.         return;
  61.     if (s == e)
  62.     {
  63.         cur->val = prev->val + v;
  64.         return;
  65.     }
  66.     int m = (s + e) / 2;
  67.     if (i <= m)
  68.     {
  69.         cur->r = prev->r;
  70.         cur->l = new node();
  71.         update(prev->l, cur->l, s, m, i, v);
  72.     }
  73.     else
  74.     {
  75.         cur->l = prev->l;
  76.         cur->r = new node();
  77.         update(prev->r, cur->r, m + 1, e, i, v);
  78.     }
  79.     cur->val = cur->l->val + cur->r->val;
  80. }
  81.  
  82. int query(node *u, node *v, node *lc, node *lcp, int cnt, int s, int e)
  83. {
  84.     if (s == e)
  85.         return s;
  86.     int m = (s + e) / 2;
  87.     int cc = u->l->val + v->l->val - lc->l->val - lcp->l->val;
  88.     if (cc >= cnt)
  89.         return query(u->l, v->l, lc->l, lcp->l, cnt, s, m);
  90.     else
  91.         return query(u->r, v->r, lc->r, lcp->r, cnt - cc, m + 1, e);
  92. }
  93.  
  94. // LCA
  95.  
  96. void dfs(int s, int p)
  97. {
  98.  
  99.     if (p == -1)
  100.         dep[s] = 0;
  101.     else
  102.         dep[s] = dep[p] + 1;
  103.  
  104.     par[0][s] = p;
  105.  
  106.  
  107.     vrsn[s + 1] = new node();
  108.     update(vrsn[p + 1], vrsn[s + 1], 0, k - 1, comp[s], 1);
  109.     for (auto it : adj[s])
  110.     {
  111.         if (it != p)
  112.             dfs(it, s);
  113.     }
  114.  
  115. }
  116.  
  117. void pre()
  118. {
  119.     for (int i = 1; i < 21; i++)
  120.     {
  121.         for (int j = 0; j < n; j++)
  122.         {
  123.             if (par[i - 1][j] != -1)
  124.                 par[i][j] = par[i - 1][par[i - 1][j]];
  125.         }
  126.     }
  127. }
  128.  
  129. int lca(int u, int v)
  130. {
  131.  
  132.     if (dep[v] > dep[u])
  133.         swap(u, v);
  134.  
  135.     if (dep[u] > dep[v])
  136.     {
  137.         for (int i = 0; i < 22; i++)
  138.         {
  139.             if ((dep[u] >> i) & 1)
  140.                 u = par[i][u];
  141.         }
  142.     }
  143.  
  144.     if (u == v)    return v;
  145.  
  146.     for (int i = 21; i > -1; i--)
  147.     {
  148.         if (par[i][u] != par[i][v])
  149.         {
  150.             u = par[i][u];
  151.             v = par[i][v];
  152.         }
  153.     }
  154.  
  155.     return par[0][u];
  156.  
  157. }
  158.  
  159. int main()
  160. {
  161.     ios::sync_with_stdio(0);
  162.     cin.tie(0); cout.tie(0);
  163. #ifndef ONLINE_JUDGE
  164.     freopen("input.txt", "r", stdin);
  165.     freopen("output.txt", "w", stdout);
  166. #endif
  167.  
  168.     int q, l, r, c, lc, lcp;
  169.  
  170.     SFD(n); SFD(q);
  171.  
  172.     FOR(i, 0, n)
  173.     {
  174.         SFD(wt[i]);
  175.         temp[i] = wt[i];
  176.     }
  177.  
  178.     sort(temp, temp + n);
  179.     k = unique(temp, temp + n) - temp;
  180.  
  181.     FOR(i, 0, n)
  182.     {
  183.         comp[i] = lower_bound(temp, temp + n, wt[i]) - temp;
  184.         rm[comp[i]] = wt[i];
  185.     }
  186.  
  187.     FOR(i, 0, n - 1)
  188.     {
  189.         SFD(l); SFD(r);
  190.         l--; r--;
  191.         adj[l].PB(r);
  192.         adj[r].PB(l);
  193.     }
  194.  
  195.     memset(par, -1, sizeof(par));
  196.  
  197.     vrsn[0] = new node();
  198.     build(0, k - 1, vrsn[0]);
  199.  
  200.     dfs(0, -1);
  201.  
  202.     pre();
  203.  
  204.     while (q--)
  205.     {
  206.         SFD(l); SFD(r); SFD(c);
  207.         l--; r--;
  208.         lc = lca(l, r);
  209.         lcp = par[0][lc];
  210.         cout << rm[query(vrsn[l + 1], vrsn[r + 1], vrsn[lc + 1], vrsn[lcp + 1], c, 0, k - 1)] << endl;
  211.     }
  212.  
  213.  
  214.  
  215.     return 0;
  216. }
Success #stdin #stdout 0s 16996KB
comments (?)
stdin
copy 
7 7
4 10 2 2 5 5 4
1 2
2 3
3 4
4 5
5 6
6 7
1 7 1
1 7 2
1 7 3
1 7 4
1 7 5
1 7 6
1 7 7
stdout
copy 
2
2
4
4
5
5
10
https://ideone.com/f7gzOw
problem COT, based on SPOJ submission 25925250 (CPP), 2020-05-06 14:07:02
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!