#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(){
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
/*
* Get dates about fountain.
* Creating array in witch every number denotes index of the nearest number witch greater than this reservoir.
* Indexes in this array means number of reservoir.
*/
int copy_height, copy_queries;
int streams_number = 0;
scanf("%d%d", ©_height, ©_queries);
const int height = copy_height, queries = copy_queries;
int diameters[height], next_grater[height], capacities[height + 1];
capacities[height] = 0;
vector <int> starts;
stack <int> meowmeow;
for (int i = 0; i < height; i++){
scanf("%d%d", &diameters[i], &capacities[i]);
if (!meowmeow.empty() && diameters[i] > diameters[meowmeow.top()]){
do{
next_grater[meowmeow.top()] = i;
meowmeow.pop();
}while (!meowmeow.empty() && diameters[i] > diameters[meowmeow.top()]);
}
else{
streams_number++;
starts.push_back(i);
}
meowmeow.push(i);
}
while (!meowmeow.empty()){
next_grater[meowmeow.top()] = height;
meowmeow.pop();
}
/*
* Creating of any possible water path.
*/
int affiliation[height], indexes[height];
int lengths[streams_number] {};
vector <int> streams[streams_number];
for (int i = 0; i < streams_number; i++){
for (int j = starts[i], k = 0; j != height; j = next_grater[j], k++) {
streams[i].push_back(j);
lengths[i]++;
indexes[j] = k;
affiliation[j] = i;
}
streams[i].push_back(height);
}
/*
* Creating postfix sums array.
*/
for (int i = height - 1; i > -1; i--){
capacities[i] += capacities[next_grater[i]];
}
/*
* Get queries and by binary search print answer.
*/
int volume, level, left, right, middle, answer;
while (queries--){
scanf("%d%d", &level, &volume);
level--;
left = indexes[level] + 1, right = lengths[affiliation[level]], answer = streams[affiliation[level]][indexes[level]] + 1;
while (left - right < 1){
middle = (left + right) / 2;
if (volume > capacities[level] - capacities[streams[affiliation[level]][middle]]){
answer = streams[affiliation[level]][middle] + 1;
left = middle + 1;
} else {
right = middle - 1;
}
}
printf("%d\n", answer % (height + 1));
}
}
Compilation message
fountain.cpp: In function 'int main()':
fountain.cpp:65:12: error: decrement of read-only variable 'queries'
65 | while (queries--){
| ^~~~~~~
fountain.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d%d", ©_height, ©_queries);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d%d", &diameters[i], &capacities[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d%d", &level, &volume);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
