Buongiorno a tutti, scrivo qui per chiedere aiuto su police7. Ho cercato di risolverlo implementando un segment tree iterativo, ma riesco a superare solo l’esempio, il subtask 3 e il 4. Nel subtask 2 dà alcuni output errati (e per quanto ci abbia sbattuto la testa sopra, non riesco proprio a capire il motivo 
), mentre il 5 e il 6 vanno in TLE. Vi allego qui di seguito il mio codice:
// NOTE: it is recommended to use this even if you don't understand the following code.
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int N, Q;
vector<int> tree;
int query(int l, int r, int *pos) {
l += N;
r += N;
int ma = -999;
while (l <= r) {
if (l%2==1) {
if (tree[l] > ma) {
ma = tree[l];
*pos = l;
}
l++;
}
if (r%2==0) {
if (tree[r] > ma) {
ma = tree[r];
*pos = r;
}
r--;
}
l/=2;
r/=2;
}
while (*pos < N) {
*pos*=2;
if (tree[*pos]!=ma) *pos+=1;
}
*pos-=N;
return ma;
}
int main() {
// uncomment the following lines if you want to read/write from files
ifstream cin("input.txt");
ofstream cout("output.txt");
cin >> N >> Q;
tree.resize(2*N);
vector<int> S(N);
for (int i = N; i < 2*N; i++) {
cin >> tree[i];
}
for (int i = N-1; i > 0; i--) {
tree[i] = max(tree[i*2], tree[i*2+1]);
}
for (int q = 0; q < Q; q++) {
int p, s;
cin >> p >> s;
p += N;
tree[p] = s;
for (p/=2; p > 0; p/=2) {
tree[p] = max(tree[p*2], tree[p*2+1]);
}
// insert your code here
long long res = 0;
int newRes = -999;
int prevRes = -9999;
int l = 0;
while (l < N-1) {
newRes = query(l+1, N-1, &l);
if (newRes != prevRes) res += newRes;
prevRes = newRes;
}
// print the result
cout << res << '\n';
}
return 0;
}
Grazie a chiunque riesca ad aiutarmi 
. Tutt’ora non mi capacito di come abbia fatto a non accorgermene… 