Submission #226905

#	Time	Username	Problem	Language	Result	Execution time	Memory
226905		errorgorn	Fire (JOI20_ho_t5)	C++14	100 / 100	883 ms	71904 KiB

ho_t5

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
struct dat{
	ll val=0,lazy=0;
	
	dat(){}
};

struct node{
	dat seg[1050000];

	ll propo(int u,int s,int e){
		if (seg[u].lazy){
			seg[u].val+=seg[u].lazy*(e-s+1);
			if (s!=e) seg[u<<1].lazy+=seg[u].lazy,seg[u<<1|1].lazy+=seg[u].lazy;
			seg[u].lazy=0;
		}
		
		return seg[u].val;
	}

	void update(int i,int j,ll k,int u=1,int s=-200005,int e=200005){
		//cerr<<i<<" "<<j<<" "<<k<<" "<<u<<" "<<s<<" "<<e<<endl;
		int m=s+e>>1;
		
		if (s==i && e==j){
			seg[u].lazy+=k;
		}
		else{	
			if (j<=m) update(i,j,k,u<<1,s,m);
			else if (m<i) update(i,j,k,u<<1|1,m+1,e);
			else update(i,m,k,u<<1,s,m),update(m+1,j,k,u<<1|1,m+1,e);
			
			seg[u].val=propo(u<<1,s,m)+propo(u<<1|1,m+1,e);	
		}
	}

	ll query(int i,int j,int u=1,int s=-200005,int e=200005){
		propo(u,s,e);
		
		int m=s+e>>1;
		
		if (s==i && e==j) return seg[u].val;
		else if (j<=m) return query(i,j,u<<1,s,m);
		else if (m<i) return query(i,j,u<<1|1,m+1,e);
		else return query(i,m,u<<1,s,m)+query(m+1,j,u<<1|1,m+1,e);
	}
}rect=node(),diag=node();

struct upd{
	int row;
	int s,e;
	ll val;
	
	upd(int a,int b,int c,ll d){
		row=a,s=b,e=c,val=d;
	}
};

struct Q{
	int a,b,c;
	int index;
	
	Q(int _a,int _b,int _c,int _index){
		a=_a,b=_b,c=_c,index=_index;
	}
};

int n,q;
int arr[200005];
int l[200005];
int r[200005];

vector<int> stk;

vector<upd> ru;
vector<upd> du;

vector<Q> queries;

ll ans[200005];

void tri(int i,int j,ll val){
	//cout<<i<<" "<<j<<" "<<val<<endl;
	if (j<i) return; //stupid shit

	
	diag.update(i,200005,val);
	rect.update(j+1,200005,-val);
	
	du.push_back(upd(j-i,i,200005,val));
	ru.push_back(upd(j-i,j+1,200005,-val));
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q;
	rep(x,1,n+1) cin>>arr[x];
	
	rep(x,1,n+1){
		while (!stk.empty() && arr[stk.back()]<arr[x]){
			r[stk.back()]=x-1;
			stk.pop_back();
		}
		
		stk.push_back(x);
	}
	while (!stk.empty()){
		r[stk.back()]=n;
		stk.pop_back();
	}
	
	rep(x,n+1,1){
		while (!stk.empty() && arr[stk.back()]<=arr[x]){
			l[stk.back()]=x+1;
			stk.pop_back();
		}
		
		stk.push_back(x);
	}
	while (!stk.empty()){
		l[stk.back()]=-200005; //yea
		stk.pop_back();
	}
	
	rep(x,1,n+1){
		tri(l[x],x-1,-arr[x]);
		tri(x+1,r[x],-arr[x]);
		tri(l[x],r[x],arr[x]);
	}
	
	int a,b,c;
	rep(x,0,q){
		cin>>a>>b>>c;
		
		queries.push_back(Q(a,b,c,x));
	}
	
	sort(all(queries),[](Q &i,Q &j){
		return i.a<j.a;
	});
	
	sort(all(du),[](upd &i,upd &j){
		return i.row>j.row;
	});
	
	sort(all(ru),[](upd &i,upd &j){
		return i.row>j.row;
	});
	
	for (auto &it:queries){
		while (!du.empty() && du.back().row<it.a){
			diag.update(du.back().s,du.back().e,-du.back().val);
			du.pop_back();
		}
		
		while (!ru.empty() && ru.back().row<it.a){
			rect.update(ru.back().s,ru.back().e,-ru.back().val);
			ru.pop_back();
		}
		
		ans[it.index]=rect.query(it.b,it.c)+diag.query(it.b-it.a,it.c-it.a);
	}
	
	rep(x,0,q) cout<<ans[x]<<endl;
}

Compilation message (stderr)

ho_t5.cpp: In member function 'void node::update(int, int, long long int, int, int, int)':
ho_t5.cpp:49:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
ho_t5.cpp: In member function 'long long int node::query(int, int, int, int, int)':
ho_t5.cpp:66:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~

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