Submission #226806

#	Time	Username	Problem	Language	Result	Execution time	Memory
226806		errorgorn	Fire (JOI20_ho_t5)	C++14	1 / 100	375 ms	262148 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<ii,ll>
#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 node1d{
	int s,e,m;
	ll val=0,lazy=0;
	node1d *l=nullptr,*r=nullptr;
	node1d(int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
	}
	
	ll propo(){
		val+=lazy*(e-s+1);
		if (s!=e){
			if (l==nullptr) l=new node1d(s,m),r=new node1d(m+1,e);
			l->lazy+=lazy,r->lazy+=lazy;
		}
		lazy=0;
		
		return val;
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			propo();
			
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			val=l->propo()+r->propo();
		}
	}
	
	ll query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else{			
			if (j<=m) return l->query(i,j);
			else if (m<i) return r->query(i,j);
			else return l->query(i,m)+r->query(m+1,j);
		}
	}
};

struct node2d{
	int s,e,m;
	node1d *seg=new node1d(-200005,200005);
	node2d *l,*r;
	
	node2d(int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node2d(s,m);
			r=new node2d(m+1,e);
		}
	}
	
	void update(int i,int j,int i2,int j2,ll k){
		if (s==i && e==j) seg->update(i2,j2,k);
		else if (j<=m) l->update(i,j,i2,j2,k);
		else if (m<i) r->update(i,j,i2,j2,k);
		else l->update(i,m,i2,j2,k),r->update(m+1,j,i2,j2,k);
	}
	
	ll query(int i,int i2,int j2){ //we are only querying for a single slice
		//cout<<s<<" "<<e<<" "<<seg->query(i2,j2)<<endl;
		if (s==e) return seg->query(i2,j2);
		else if (i<=m) return seg->query(i2,j2)+l->query(i,i2,j2);
		else return seg->query(i2,j2)+r->query(i,i2,j2);
	}
}*rect=new node2d(0,400005),*diag=new node2d(0,400005);

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

vector<int> stk;

void tri(int i,int j,ll val){
	//cout<<i<<" "<<j<<" "<<val<<endl;
	if (j<i) return; //stupid shit
	
	diag->update(0,j-i,i,200005,val);
	rect->update(0,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;
	while (q--){
		cin>>a>>b>>c;
		
		//debug(rect->query(a,b,c));
		//debug(diag->query(a,b-a,c-a));
		
		cout<<rect->query(a,b,c)+diag->query(a,b-a,c-a)<<endl;
	}
}

Compilation message (stderr)

ho_t5.cpp: In constructor 'node1d::node1d(int, int)':
ho_t5.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~
ho_t5.cpp: In constructor 'node2d::node2d(int, int)':
ho_t5.cpp:79:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

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