Submission #1166308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166308		mertbbm	Fire (JOI20_ho_t5)	C++20	100 / 100	756 ms	152872 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

struct qq{
	int index,t,l,r;
};

inline int combine(int a, int b){
	return a+b;
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int lazyUpd;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_add(int x){
		v+=(e-s+1)*x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd); r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

vector<array<int,3>>storage2[200005]; //normal
vector<array<int,3>>storage3[200005]; //triangle


void f(int index, int a, int sgn, int ptr){
	a=min(a,index-1);
	if(a<0) return;
	//normal
	int hold=index-a;
	storage2[hold].push_back({a,sgn,ptr});
	//triangle
	storage3[hold].push_back({a+hold,sgn*-1,ptr});
	storage3[index].push_back({hold+a,sgn,ptr});
}

void solve(){
	int n,q;
	cin >> n >> q;
	
	int arr[n+5];
	for(int x=1;x<=n;x++){
		cin >> arr[x];
	}
	
	qq que[q];
	for(int x=0;x<q;x++){
		cin >> que[x].t >> que[x].l >> que[x].r;
		que[x].index=x;
		f(que[x].r,que[x].t,1,x);
		f(que[x].l-1,que[x].t,-1,x);
	}
	
	vector<int>d;
	vector<pair<pii,int>>storage[n+5]; //add
	d.push_back(n+1);
	
	for(int x=n;x>=1;x--){
		storage[x].push_back({{0,0},arr[x]});
		int cur=0;
		while(d.size()>1&&arr[d.back()]<arr[x]){
			int hold=d.back();
			d.pop_back();
			int diff=d.back()-hold;
			storage[x].push_back({{cur+1,cur+diff},arr[x]-arr[hold]});
			cur+=diff;
		}
		d.push_back(x);
	}
	
	node st(0,n+5); //normal
	node st2(0,2*n+5); //triangular
	
	int ans[q];
	memset(ans,0,sizeof(ans));

	for(int x=0;x<=n;x++){
		for(auto it:storage[x]){
			st.rangeUpd(it.first.first,it.first.second,it.second);
			st2.rangeUpd(it.first.first+x,it.first.second+x,it.second);
		}
		for(auto it:storage2[x]){
			ans[it[2]]+=st.query(0,it[0])*it[1];
		}
		
		for(auto it:storage3[x]){
			ans[it[2]]+=st2.query(0,it[0])*it[1];
		}
	}
	
	for(int x=0;x<q;x++){
		cout << ans[x] << "\n";
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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