Submission #1326710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326710		joacru	Fire (JOI20_ho_t5)	C++20	100 / 100	735 ms	68052 KiB

ho_t5

#include <bits/stdc++.h>

#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()

#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)

#define LINE cerr<<"===================================="<<endl

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
	os<<"[";
	forn(i,v.size()){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;
typedef long double ld;

struct ST{
	int n;
	vector<ll> st, lz;
	ST(int _n){
		n = 1<<(32-__builtin_clz(_n-1));
		st.resize(2*n-1);
		lz.resize(2*n-1);
	}
	void push(int i, int l, int r){
		if(!lz[i]) return;
		st[i] += lz[i]*(r-l);
		if(i<n-1){
			lz[2*i+1] += lz[i];
			lz[2*i+2] += lz[i];
		}
		lz[i] = 0;
	}
	void update(int ul, int ur, int v, int l, int r, int i){
		push(i,l,r);
		if(l>=ur||r<=ul) return;
		if(l>=ul&&r<=ur){
			lz[i] += v;
			push(i,l,r);
			return;
		}
		int m=(l+r)/2;
		update(ul,ur,v,l,m,2*i+1);
		update(ul,ur,v,m,r,2*i+2);
		st[i] = st[2*i+1]+st[2*i+2];
	}
	void update(int l, int v){ // creo que no es necesario r
		update(l,n,v,0,n,0);
	}
	ll query(int ql, int qr, int l, int r, int i){
		push(i,l,r);
		if(l>=qr||r<=ql) return 0;
		if(l>=ql&&r<=qr) return st[i];
		int m=(l+r)/2;
		return query(ql,qr,l,m,2*i+1)+query(ql,qr,m,r,2*i+2);
	}
	ll query(int l, int r){
		return query(l,r,0,n,0);
	}
	void print(int l, int r, int i){
		push(i,l,r);
		if(i >= n-1){
			cout<<st[i]<<" ";
			return;
		}
		int m = (l+r)/2;
		print(l,m,2*i+1);
		print(m,r,2*i+2);
	}
	void print(){
		print(0,n,0);
		cout<<"\n";
	}
};

struct Update{
	int d, t, l, v; // d: diagonal
	bool operator<(const Update&o)const{
		return t < o.t;
	}
};

struct Query{
	int i, t, l, r;
	bool operator<(const Query&o)const{
		return t < o.t;
	}
};

void solve(){
	
	int n, q;
	cin>>n>>q;
	vector<int> s(n);
	for(int &x: s) cin>>x;
	
	// procesar todo
	
	vector<int> toLeft(n), toRight(n);
	auto comp = [](int a, int b, int i){
		if(i == 0) return a < b;
		return a <= b;
	};
	forn(_,2){
		stack<int> nge;
		forn(i,n){
			while(SZ(nge) && comp(s[nge.top()], s[i], _)) nge.pop();
			if(SZ(nge)) toLeft[i] = nge.top();
			else toLeft[i] = -1;
			nge.push(i);
		}
		reverse(ALL(s));
		swap(toLeft, toRight);
	}
	reverse(ALL(toRight));
	for(int &x: toRight) x = n-x-1;
	//~ DBG2(toLeft, toRight);
	
	vector<Update> upds;
	
	// calcular updates
	
	const int D = n+2;
	
	auto getTriangle = [&](int i, int h, int v){
		if(!h) return;
		// diagonal
		upds.push_back({1, 0, i+D, +v});
		upds.push_back({1, h, i+D, -v});
		// vertical
		upds.push_back({0, 0, i+D+h, -v});
		upds.push_back({0, h, i+D+h, +v});
	};
	
	auto getParallelogram = [&](int i){ // obtiene el paralelogramo del i-esimo elemento
		int l = toLeft[i] + 1; // aqui empieza su triangulo
		if(l == 0) l -= D;
		//~ DBG(toLeft[i]);
		int r = toRight[i]; // es exclusivo
		int h = r - l; // tamaño del triangulo
		getTriangle(l,h,s[i]);
		getTriangle(l,i-l,-s[i]);
		getTriangle(i+1,r-i-1,-s[i]);
	};
	
	forn(i,n) getParallelogram(i);
	
	sort(ALL(upds));
	
	// cargar y ordenar queries
	
	vector<Query> qrs(q);
	forn(i,q){
		int t,l,r;
		cin>>t>>l>>r;
		--l;
		qrs[i] = {i, t, l, r};
	}
	
	sort(ALL(qrs));
	
	// responder queries
	
	int j = 0;
	ST diag(2*n+5), vert(2*n+5);
	vector<ll> ans(q);
	for(Query &Q: qrs){
		while(j < SZ(upds) && upds[j].t <= Q.t){
			Update &U = upds[j];
			if(U.d) diag.update(U.l, U.v);
			else vert.update(U.l, U.v);
			++j;
			//~ if(U.v != 0) DBG4(U.d, U.t, U.l, U.v);
			//~ if(U.v != 0) diag.print();
			//~ if(U.v != 0) vert.print();
		}
		//~ DBG4("listo para procesar", Q.t, Q.l, Q.r);
		ll a = vert.query(Q.l+D, Q.r+D);
		ll b = diag.query(Q.l+D-Q.t, Q.r+D-Q.t);
		ans[Q.i] = a+b;
	}
	
	for(ll x: ans) cout<<x<<"\n";
	
	cerr<<"===============\n";
	
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
		assert(freopen("input.in", "r", stdin));
		//~ freopen("output.out", "w", stdout);
	#endif
	
	#ifdef LOCAL
	int tcs; cin>>tcs;
	while(tcs--)
	#endif
	solve();

	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80