oj.uz

Submission #349896

# Submission time Handle Problem Language Result Execution time Memory
349896 2021-01-18T16:06:51 Z YJU Fire (JOI20_ho_t5) C++14
6 / 100
 927 ms 55312 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=(1LL<<19);
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct Segment_Tree{
	ll sum[4*N];
	int tag[4*N];
	void push(int id,int l,int r){
		if(tag[id]){
			ll mid=(l+r)>>1;
			sum[id*2]+=(mid-l)*tag[id];
			sum[id*2+1]+=(r-mid)*tag[id];
			tag[id*2]+=tag[id];
			tag[id*2+1]+=tag[id];
			tag[id]=0;
		}
	}
	void add(int id,int l,int r,int ql,int qr,ll val){
		if(l>=qr||r<=ql)return ;
		if(l>=ql&&r<=qr){tag[id]+=val;sum[id]+=val*(r-l);return;}
		push(id,l,r);
		ll mid=(l+r)>>1;
		add(id*2,l,mid,ql,qr,val);
		add(id*2+1,mid,r,ql,qr,val);
		sum[id]=sum[id*2]+sum[id*2+1];
	}
	ll ask(int id,int l,int r,int ql,int qr){
		if(l>=qr||r<=ql)return 0;
		if(l>=ql&&r<=qr)return sum[id];
		push(id,l,r);
		ll mid=(l+r)>>1;
		return ask(id*2,l,mid,ql,qr)+ask(id*2+1,mid,r,ql,qr);
	}
	
	
}seg1,seg2;

int n,q,a[N],sz=0,stk[N],L[N],R[N];
ll ans[N];
vector<pair<int,pair<int,int> > > query[N];
vector<pair<pair<int,int>,int> > work[N];

ll Q(int t,int r){
	return seg1.ask(1,0,N,1,r-t+1+N/2)+seg2.ask(1,0,N,1,r+1+N/2);
}

void update(int ql,int qr,ll val){
	seg1.add(1,0,N,ql+N/2,N,val);
	seg2.add(1,0,N,qr+1+N/2,N,-val);
}

void build(int ql,int qr,ll val){
	if(ql>qr)return ;
	work[0].pb(mp(mp(ql,qr),val));
	work[qr-ql+1].pb(mp(mp(ql,qr),-val));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	REP1(i,n){
		cin>>a[i];
		while(sz&&a[stk[sz]]<=a[i]){
			R[stk[sz]]=i;
			--sz;
		}
		L[i]=(sz==0?-n-1:stk[sz]);
		R[i]=n+1;
		stk[++sz]=i;
	}

	REP1(i,q){
		ll t,x,y;
		cin>>t>>x>>y;
		query[t].pb(mp(i,mp(x,y)));
	}
	
	REP1(i,n){
		build(L[i]+1,i-1,-a[i]);
		build(i+1,R[i]-1,-a[i]);
		build(L[i]+1,R[i]-1,a[i]);
	}
	
	REP(i,n+1){
		for(auto k:work[i]){
			update(k.X.X,k.X.Y,k.Y);
		}
		for(auto k:query[i]){
			ans[k.X]=Q(i,k.Y.Y)-Q(i,k.Y.X-1);
		}
	}
	REP1(i,q)cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Incorrect 18 ms 25324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Incorrect 863 ms 53748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Incorrect 927 ms 55312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 53648 KB Output is correct
2 Correct 835 ms 54032 KB Output is correct
3 Correct 856 ms 54544 KB Output is correct
4 Correct 846 ms 53648 KB Output is correct
5 Correct 830 ms 54160 KB Output is correct
6 Correct 836 ms 53904 KB Output is correct
7 Correct 830 ms 54288 KB Output is correct
8 Correct 843 ms 54032 KB Output is correct
9 Correct 840 ms 53904 KB Output is correct
10 Correct 836 ms 54288 KB Output is correct
11 Correct 847 ms 53904 KB Output is correct
12 Correct 838 ms 54032 KB Output is correct
13 Correct 841 ms 53904 KB Output is correct
14 Correct 845 ms 54288 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Incorrect 18 ms 25324 KB Output isn't correct
3 Halted 0 ms 0 KB -