// UVa 11235 - Frequent values #include <iostream> #include <vector> using namespace std; struct node { node *left, *right; int max_freq; int ini, fin; int mid; }; int find(int a, int b, node *nd) { if (nd->right == NULL && nd->left == NULL) return min(nd->max_freq, min(b, nd->fin) - max(a, nd->ini) + 1); if (nd->ini == a && nd->fin == b) return nd->max_freq; if (nd->right == NULL || nd->mid >= b) return find(a, b, nd->left); if (nd->mid < a) return find(a, b, nd->right); int l = find(a, nd->mid, nd->left); int r = find(nd->mid + 1, b, nd->right); return max(l, r); } int main() { int n, q; while ((cin >> n >> q) && n) { int b; node *nd = new node; vector<node*> this_lvl; nd->ini = 1; nd->max_freq = 1; for (int i = 1; i <= n; i++) { int a; cin >> a; if (i > 1 && a == b) nd->max_freq++; else if (i > 1 && a != b) { nd->fin = i - 1; nd->mid = 0; nd->left = NULL; nd->right = NULL; this_lvl.push_back(nd); nd = new node; nd->ini = i; nd->max_freq = 1; } b = a; } nd->fin = n; nd->mid = 0; nd->left = NULL; nd->right = NULL; this_lvl.push_back(nd); // build tree while (this_lvl.size() > 1) { vector<node*> next_lvl; for (int i = 0; i < this_lvl.size(); i += 2) { int j = (i + 1 < this_lvl.size()) ? i + 1 : i; node *nd = new node; nd->ini = this_lvl[i]->ini; nd->fin = this_lvl[j]->fin; nd->max_freq = max(this_lvl[i]->max_freq, this_lvl[j]->max_freq); nd->mid = this_lvl[i]->fin; nd->left = this_lvl[i]; nd->right = (i != j) ? this_lvl[j] : NULL; next_lvl.push_back(nd); } this_lvl = next_lvl; } node* root = this_lvl[0]; // queries for (; q; q--) { int a, b; cin >> a >> b; cout << find(a, b, root) << endl; } } return 0; }
Tuesday, December 1, 2015
UVa 11235 - Frequent values
Subscribe to:
Post Comments (Atom)
Do random comments get deleted?
ReplyDeleteApparently, no
Delete