Implement a segment tree (segtree) 0/100

Aiuto
1

dopo aver passato svariate ore su questo problema sono finalmente riuscito a risolvere l’esempio di questo problema, ma andando avanti coi test trovo principalmente errori di tempo (execution timed out) e qualche “incorrect output” nelle subtask 4, 5 e 6. Si purtroppo è tanta roba, infatti il risultato è 0/100, e per questo mi servirebbe una grande mano.

#include <vector>
#include <limits>
#include <climits>

using namespace std;

struct Node{
	long long val_sum;
	long long val_min;
	long long left;
	long long lazy_add;
	long long lazy_set;
	int set_last;

	Node() : val_sum(0), val_min(LLONG_MAX), left(LLONG_MAX), lazy_add(0), lazy_set(LLONG_MIN), set_last(0) {};

	void join(const Node &l, const Node &r){
		val_min = min(l.val_min, r.val_min);
		val_sum = l.val_sum + r.val_sum;
		left = l.left;
	}
};

int n, real_size;
vector<Node> nodes;

void build(int u, int l, int r, vector<long long> a){
	if(r - l == 1){
		if(l < a.size()){
			nodes[u].val_sum = a[l];
			nodes[u].val_min = a[l];
			nodes[u].left = a[l];
		}
	}
	else{
		build(2*u, l, (l+r)/2, a);
		build(2*u+1, (l+r)/2, r, a);
		nodes[u].join(nodes[2*u],nodes[2*u+1]);
	}
}

void init(vector<long long> a) {
	n = a.size();
	real_size = 1;
	while(real_size < n)
		real_size *= 2;

	nodes.assign(2*real_size, Node());

	build(1, 0, real_size, a);
}

void checkLazy(int u, int l, int r){ 
	if(nodes[u].lazy_add != 0 && nodes[u].lazy_set != LLONG_MIN){
		if(nodes[u].set_last){
			nodes[u].val_sum = (r - l) * nodes[u].lazy_set;
			nodes[u].val_min = nodes[u].lazy_set;
			nodes[u].left = nodes[u].lazy_set;
			if(r - l != 1){
				nodes[u*2].lazy_set = nodes[u].lazy_set;
				nodes[u*2+1].lazy_set = nodes[u].lazy_set;
				nodes[u*2].lazy_add = 0;
				nodes[u*2+1].lazy_add = 0;
				nodes[u*2].set_last = nodes[u].set_last;
				nodes[u*2+1].set_last = nodes[u].set_last;
			}
		}
		else{
			nodes[u].val_sum = (r - l) * (nodes[u].lazy_set + nodes[u].lazy_add);
			nodes[u].val_min = nodes[u].lazy_set + nodes[u].lazy_add;
			nodes[u].left = nodes[u].lazy_set + nodes[u].lazy_add;
			if(r - l != 1){
				nodes[u*2].lazy_set = nodes[u].lazy_set;
				nodes[u*2+1].lazy_set = nodes[u].lazy_set;
				nodes[u*2].lazy_add = nodes[u].lazy_add;
				nodes[u*2+1].lazy_add = nodes[u].lazy_add;
				nodes[u*2].set_last = nodes[u].set_last;
				nodes[u*2+1].set_last = nodes[u].set_last;
			}
		}
		nodes[u].lazy_set = LLONG_MIN;
		nodes[u].lazy_add = 0;
		nodes[u].set_last = 0;
	}
	else{
		if(nodes[u].lazy_add != 0){
			nodes[u].val_sum += (r - l) * nodes[u].lazy_add;
			nodes[u].val_min += nodes[u].lazy_add;
			nodes[u].left += nodes[u].lazy_add;
			if(r - l != 1){
				nodes[u*2].lazy_add += nodes[u].lazy_add;
				nodes[u*2+1].lazy_add += nodes[u].lazy_add;
			}
			nodes[u].lazy_add = 0;
		}
		if(nodes[u].lazy_set != LLONG_MIN){
			nodes[u].val_sum = (r - l) * nodes[u].lazy_set;
			nodes[u].val_min = nodes[u].lazy_set;
			nodes[u].left = nodes[u].lazy_set;
			if(r - l != 1){
				nodes[u*2].lazy_set = nodes[u].lazy_set;
				nodes[u*2+1].lazy_set = nodes[u].lazy_set;
				nodes[u*2].lazy_add = 0;
				nodes[u*2+1].lazy_add = 0;
			}
			nodes[u].lazy_set = LLONG_MIN;
		}		
	}
}

long long get_sum(int u, int l, int r, int x, int y){
	checkLazy(u, l, r);

	if(x >= r || y <= l) return 0;
	if(l >= x && r <= y) return nodes[u].val_sum;

	return get_sum(2*u, l, (l+r)/2, x, y) + get_sum(2*u+1, (l+r)/2, r, x, y);
}

long long get_sum(int l, int r) {
	return get_sum(1, 0, real_size, l, r);
}

void add(int u, int l, int r, int x, int y, long long val){
	checkLazy(u, l, r);
	if(x >= r || y <= l) return;
	if(l >= x && r <= y){
		nodes[u].val_sum += (r - l) * val;
		nodes[u].val_min += val;
		nodes[u].left += val;
		if(r - l != 1){
			nodes[2*u].lazy_add += val;
			nodes[2*u+1].lazy_add += val;
		}
		return;
	}
	add(2*u, l, (l+r)/2, x, y, val);
	add(2*u+1, (l+r)/2, r, x, y, val);
	nodes[u].join(nodes[2*u],nodes[2*u+1]);
}

void add(int l, int r, long long x) {
	add(1,0, real_size, l, r, x);
}

void set_range(int u, int l, int r, int x, int y, long long val){
	checkLazy(u, l, r);
	if(x >= r || y <= l) return;
	if(l >= x && r <= y){
		nodes[u].val_sum = (r - l) * val;
		nodes[u].val_min = val;
		nodes[u].left = val;
		if(r - l != 1){
			nodes[2*u].lazy_set = val;
			nodes[2*u+1].lazy_set = val;
			nodes[2*u].set_last = 1;
			nodes[2*u+1].set_last = 1;
		}
		return;
	}
	set_range(2*u, l, (l+r)/2, x, y, val);
	set_range(2*u+1, (l+r)/2, r, x, y, val);
	nodes[u].join(nodes[2*u],nodes[2*u+1]);
}

void set_range(int l, int r, long long x) {
	set_range(1,0, real_size, l, r, x);
}

long long get_min(int u, int l, int r, int x, int y){
	checkLazy(u, l, r);

	if(x >= r || y <= l) return LLONG_MAX;
	if(l >= x && r <= y) return nodes[u].val_min;

	return min(
		get_min(2*u, l, (l+r)/2, x, y),
		get_min(2*u+1, (l+r)/2, r, x, y)
	);
}

long long get_min(int l, int r) {
	return get_min(1, 0, real_size, l, r);
}

int lower_bound(int u, int l, int r, int x, int y, long long lim){
	if(x >= r || y <= l) return -1;
	if(l >= x && r <= y) return nodes[u].left < lim ? u : -1;

	int res_left = lower_bound(2*u, l, (l+r)/2, x, y, lim);
	if(res_left != -1)
		return res_left;
	int res_right = lower_bound(2*u+1, (l+r)/2, r, x, y, lim);
	return res_right;
}

int lower_bound(int l, int r, long long x) {
	int res = lower_bound(1, 0, real_size, l, r, x);
	if(res == -1) return -1;
	while(res <= real_size) res*=2;
	return res - real_size;
}
3

Aggiornamento, ho risolto i problemi con gli output non corretti, eccetto per l’ultimo subtask, ma continuo a finire timed out

#include <vector>
#include <limits>
#include <climits>

using namespace std;

struct Node{
	long long val_sum;
	long long val_min;
	long long left;
	long long lazy_add;
	long long lazy_set;

	Node() : val_sum(0), val_min(LLONG_MAX), left(LLONG_MAX), lazy_set(LLONG_MIN), lazy_add(0) {};

	void join(const Node &l, const Node &r){
		val_min = min(l.val_min, r.val_min);
		val_sum = l.val_sum + r.val_sum;
		left = l.left;
	}
};

int n, real_size;
vector<Node> nodes;

void build(int u, int l, int r, vector<long long> a){
	if(r - l == 1){
		if(l < a.size()){
			nodes[u].val_sum = a[l];
			nodes[u].val_min = a[l];
			nodes[u].left = a[l];
		}
	}
	else{
		build(2*u, l, (l+r)/2, a);
		build(2*u+1, (l+r)/2, r, a);
		nodes[u].join(nodes[2*u],nodes[2*u+1]);
	}
}

void init(vector<long long> a) {
	n = a.size();
	real_size = 1;
	while(real_size < n)
		real_size *= 2;

	nodes.assign(2*real_size, Node());

	build(1, 0, real_size, a);
}

void checkLazy(int u, int l, int r){ 
	if(nodes[u].lazy_add != 0 && nodes[u].lazy_set != LLONG_MIN){
		nodes[u].val_sum = (r - l) * (nodes[u].lazy_set + nodes[u].lazy_add);
		nodes[u].val_min = nodes[u].lazy_set + nodes[u].lazy_add;
		nodes[u].left = nodes[u].lazy_set + nodes[u].lazy_add;
		if(r - l != 1){
			nodes[u*2].lazy_set = nodes[u].lazy_set;
			nodes[u*2+1].lazy_set = nodes[u].lazy_set;
			nodes[u*2].lazy_add = nodes[u].lazy_add;
			nodes[u*2+1].lazy_add = nodes[u].lazy_add;
		}
		nodes[u].lazy_set = LLONG_MIN;
		nodes[u].lazy_add = 0;
	}
	else{
		if(nodes[u].lazy_add != 0){
			nodes[u].val_sum += (r - l) * nodes[u].lazy_add;
			nodes[u].val_min += nodes[u].lazy_add;
			nodes[u].left += nodes[u].lazy_add;
			if(r - l != 1){
				nodes[u*2].lazy_add += nodes[u].lazy_add;
				nodes[u*2+1].lazy_add += nodes[u].lazy_add;
			}
			nodes[u].lazy_add = 0;
		}
		if(nodes[u].lazy_set != LLONG_MIN){
			nodes[u].val_sum = (r - l) * nodes[u].lazy_set;
			nodes[u].val_min = nodes[u].lazy_set;
			nodes[u].left = nodes[u].lazy_set;
			if(r - l != 1){
				nodes[u*2].lazy_set = nodes[u].lazy_set;
				nodes[u*2+1].lazy_set = nodes[u].lazy_set;
				nodes[u*2].lazy_add = 0;
				nodes[u*2+1].lazy_add = 0;
			}
			nodes[u].lazy_set = LLONG_MIN;
		}		
	}
}

long long get_sum(int u, int l, int r, int x, int y){
	checkLazy(u, l, r);

	if(x >= r || y <= l) return 0;
	if(l >= x && r <= y) return nodes[u].val_sum;

	return get_sum(2*u, l, (l+r)/2, x, y) + get_sum(2*u+1, (l+r)/2, r, x, y);
}

long long get_sum(int l, int r) {
	return get_sum(1, 0, real_size, l, r);
}

void add(int u, int l, int r, int x, int y, long long val){
	checkLazy(u, l, r);
	if(x >= r || y <= l) return;
	if(l >= x && r <= y){
		nodes[u].val_sum += (r - l) * val;
		nodes[u].val_min += val;
		nodes[u].left += val;
		if(r - l != 1){
			nodes[2*u].lazy_add += val;
			nodes[2*u+1].lazy_add += val;
		}
		return;
	}
	add(2*u, l, (l+r)/2, x, y, val);
	add(2*u+1, (l+r)/2, r, x, y, val);
	nodes[u].join(nodes[2*u],nodes[2*u+1]);
}

void add(int l, int r, long long x) {
	add(1,0, real_size, l, r, x);
}

void set_range(int u, int l, int r, int x, int y, long long val){
	checkLazy(u, l, r);
	if(x >= r || y <= l) return;
	if(l >= x && r <= y){
		nodes[u].val_sum = (r - l) * val;
		nodes[u].val_min = val;
		nodes[u].left = val;
		if(r - l != 1){
			nodes[2*u].lazy_set = val;
			nodes[2*u+1].lazy_set = val;
			nodes[2*u].lazy_add = 0;
			nodes[2*u+1].lazy_add = 0;
		}
		return;
	}
	set_range(2*u, l, (l+r)/2, x, y, val);
	set_range(2*u+1, (l+r)/2, r, x, y, val);
	nodes[u].join(nodes[2*u],nodes[2*u+1]);
}

void set_range(int l, int r, long long x) {
	set_range(1,0, real_size, l, r, x);
}

long long get_min(int u, int l, int r, int x, int y){
	checkLazy(u, l, r);

	if(x >= r || y <= l) return LLONG_MAX;
	if(l >= x && r <= y) return nodes[u].val_min;

	return min(
		get_min(2*u, l, (l+r)/2, x, y),
		get_min(2*u+1, (l+r)/2, r, x, y)
	);
}

long long get_min(int l, int r) {
	return get_min(1, 0, real_size, l, r);
}

int lower_bound(int u, int l, int r, int x, int y, long long lim){
	if(x >= r || y <= l) return -1;
	if(l >= x && r <= y) return nodes[u].left < lim ? u : -1;

	int res_left = lower_bound(2*u, l, (l+r)/2, x, y, lim);
	if(res_left != -1)
		return res_left;
	int res_right = lower_bound(2*u+1, (l+r)/2, r, x, y, lim);
	return res_right;
}

int lower_bound(int l, int r, long long x) {
	int res = lower_bound(1, 0, real_size, l, r, x);
	if(res == -1) return -1;
	while(res <= real_size) res*=2;
	return res - real_size;
}
4

Se noti il tuo codice talvolta va fuori tempo anche nei testcase dai constraints piu’ larghi, dove anche se avessi sbagliato complessita’ probabilmente staresti nei tempi
In questi casi il timeout e’ quasi sempre causato da un loop che non si chiude mai, come una ricorsione o un while che ritornano sempre su se’ stessi all’infinito.
Ti posso dare un suggerimento:

Stress testing: e’ una tecnica molto lenta ma che ti garantisce che prima o poi giungerai alla soluzione
Consiste nello scrivere un codice naive (o fartelo prestare da quancuno che ha risolto il problema), purche’ dia il risultato corretto con certezza e scrivere un piccolo pezzo di codice che generi gli input
Poi si esegue sia il codice da testare, sia il codice corretto con lo stesso input e si confrontano le differenze

5

proverò a far si che gli estremi siano entrambi inclusi, visto che ora solo quello sinistro è incluso, come specificato nel testo. intanto posso chiederti, se hai risolto il problema, di mandarmi il codice per lo stress testing?

6

Sono abbastanza in disaccordo con questa affermazione, è molto più comune tenere l’estremo destro escluso dall’intervallo e, nella mia esperienza, ho visto molti più errori causati proprio dal tenere tale estremo incluso.

Questa notazione è inoltre quella che viene usata da ogni funzione nella libreria standard (guarda ad esempio la funzione sort) e dalla maggior parte degli altri linguaggi. Il testo è stato appunto scritto proprio per incentivare l’utilizzo di questa notazione.

7

effettivamente cambiando quel dettaglio non è cambiato nulla, ma continuo a non capire come mai entri in un loop infinito

8

Grazie dell’appunto, edito il commento

9

In realtà non è detto che entri in un loop infinito, quel problema ha un limite abbastaza stretto che forsi potresti sforare con un codice poco ottimizzato (anche se non vedo cosa potrebbe farti perdere così tanto tempo). In generale ho notato che in ogni subtask c’è almeno un testcase più facile dove il mio programma riesce a fare .5 secondi sui 3 a disposizione. Vedendo i tempi sui testcase ‘facili’ (sempre che il codice li faccia) puoi capire se il programma è troppo lento per i testcase più difficili o se davvero c’è un loop infinito.

10

ma infatti credo sia un loop infinito perche il programma passa dai 0.4 s/4 Mib nei testcase semplici a 3.4s (timed out)/124 Mib nei test dopo

11

Non so se si tratta solo di un loop infinito, ma anche la tua funzione lower_bound() non fornisce un risultato corretto con questo input:

10 1
17 -15 13 27 -29 -6 -15 -29 1 -9
5 0 10 -1

12

Io ti consiglerei questo metodo che secondo me può funzionare:
Siccome non si può monitorare il codice mentre si esegue sul server e non hai a disposizione nessun input più grande puoi usare la funzione ‘abort()’: in pratica termina il programma e causa l’errore ‘execution killed with signal 6’ sul testcase. Puoi usarla in questo modo: scegli una funzione (get_sum, add, set_range…) e quando viene chiamata monitori quante volte è eseguita la funzione ricorsiva per trovare il risultato. Se questo numero dovesse superare una certa soglia (ad es. 500 volte) sai che sei entrato in un loop infinito e chiami abort(). In questo modo sai precisamente quale funzione causa il problema.

13

Effettivamente la mia soluzione non ha mai superato gli 80 MiB, quindi c’è sicurmente qualcosa che non va.