Ad hoc, Hash table
You are given N command in the following form: id, attr, val, priority. A single command C means that you have to assign the value val to attribute attr of the object with the identifier id if and only if there is no other command assigning to the same attribute of the same object with higher priority than C or with the same priority as C but listed after C in the list of commands.
After that, there are M queries of form: id, attr. Your task is to print for each of these queries the value of attribute attr of object with the identifier id.
You can store values of attributes of objects in an array of hash tables and iterate over the list of command to build and update these hash tables. After that, you can iterate over the list of queries and answer them based on data in the array.
You can use an array of hash tables h, where h[id] is a hash table representing attributes of the object with identifier id. Since 1 <= id <= 10^6 you can allocate the whole array at first. A single record in the hash table of object with identifier id h[id][attr] is a pair (val, priority) representing the value of attribute attr of the object and the priority of command which assigned the value.
You can read more about hash tables here
You can iterate over the list of all commands and update the hash tables.
for(i = 0; i < n; ++i) read id, attr, val, priority if(!h[id][attr] or h[id][attr].priority <= priority) h[id][attr].value = val h[id][attr].priority = priority
After that you can just iterate over all queries and print answers based on data stored in the hash table.
for(i = 0; i < m; ++i) read id, attr print h[id][attr]
If you use a hash table, then the time complexity is O(n), because we do only O(n) lookups and writes in it. You can also use a tree-base structure like a map in c++, for which the total complexity will be O(n log n) because a single lookup or insert into map consts O(log n). Most languages have their own implementation of a hash table. Not everyone knows that c++ also has it and it is called unordered_map.
For a partial credit, you can use a simple two dimmensional array h[id][attr] and follow the same algorithm. It can be used to solve the problem with lower constraints.