Submission #538414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538414	2022-03-16T19:25:44 Z	fcw	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	657 ms	198968 KB

apple

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;


template<typename T, typename U = int64_t>struct segtree{
	U NLIM, PLIM;
	struct node{
		U lo, hi;
		T sum, lz, l, r;
		node(U _lo = INT_MIN, U _hi = INT_MAX): lo(_lo), hi(_hi), sum(0), lz(0), l(0), r(0){}
		void merge(const node& left, const node& right){
			sum = left.sum + right.sum;
		}
		void apply(T v){
			lz = v;
			sum = (hi - lo) * v;
		}
		T get_sum(){ return sum; }
	};
	vector<node>seg;
	int create(int lo = INT_MIN, int hi = INT_MAX){
		seg.push_back(node(lo, hi));
		return (int)seg.size() - 1;
	}
	segtree(U _lo = INT_MIN, U _hi = INT_MAX): NLIM(_lo), PLIM(_hi) {
		create(NLIM, PLIM);
		create(NLIM, PLIM);
	}
	void push(int v){
		if(seg[v].lz){
			U mid = (seg[v].lo + seg[v].hi) >> 1;
			if(!seg[v].l){
				int aux = create(seg[v].lo, mid);
				seg[v].l = aux;
			}
			if(!seg[v].r){
				int aux = create(mid, seg[v].hi);
				seg[v].r = aux;
			}
			seg[seg[v].l].apply(seg[v].lz);
			seg[seg[v].r].apply(seg[v].lz);
			seg[v].lz = 0;
		}
	}

	void update(int v, U a, U b, T val){
		if(b <= seg[v].lo || seg[v].hi <= a) return;
		push(v);
		if(a <= seg[v].lo && seg[v].hi <= b){
			seg[v].apply(val);
			push(v);
			return;
		}
		U mid = (seg[v].lo + seg[v].hi) >> 1;
		if(!seg[v].l){
			int aux = create(seg[v].lo, mid);
			seg[v].l = aux;
		}
		if(!seg[v].r){
			int aux = create(mid, seg[v].hi);
			seg[v].r = aux;
		}
		update(seg[v].l, a, b, val);
		update(seg[v].r, a, b, val);
		push(seg[v].l);
		push(seg[v].r);
		seg[v].merge(seg[seg[v].l], seg[seg[v].r]);
	}
	node query(int v, U a, U b){
		if(b <= seg[v].lo || seg[v].hi <= a) return node();
		if(v == 0) return node();
		push(v);
		if(a <= seg[v].lo && seg[v].hi <= b) return seg[v];
		node e = node();
		e.merge(query(seg[v].l, a, b), query(seg[v].r, a, b));
		return e;
	}
};

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	segtree<int, int>seg(1, int(1e9 + 7));
	int n;
	cin>>n;
	int c = 0;
	for(int i=0;i<n;i++){
		int op, x, y;
		cin>>op>>x>>y;
		if(op == 2) seg.update(1, x + c, y + c + 1 , 1);
		else{
			c = seg.query(1, x + c, y + c + 1).get_sum();
			cout<<c<<"\n";
		}
	}

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	31 ms	6784 KB	Output is correct
5	Correct	34 ms	6728 KB	Output is correct
6	Correct	26 ms	6752 KB	Output is correct
7	Correct	26 ms	6784 KB	Output is correct
8	Correct	235 ms	50404 KB	Output is correct
9	Correct	456 ms	100580 KB	Output is correct
10	Correct	449 ms	100372 KB	Output is correct
11	Correct	417 ms	100312 KB	Output is correct
12	Correct	459 ms	100200 KB	Output is correct
13	Correct	375 ms	100200 KB	Output is correct
14	Correct	467 ms	100328 KB	Output is correct
15	Correct	626 ms	198888 KB	Output is correct
16	Correct	657 ms	198968 KB	Output is correct
17	Correct	415 ms	101444 KB	Output is correct
18	Correct	407 ms	101324 KB	Output is correct
19	Correct	575 ms	198936 KB	Output is correct
20	Correct	627 ms	198884 KB	Output is correct