oj.uz

Submission #349897

# Submission time Handle Problem Language Result Execution time Memory
349897 2021-01-18T16:08:59 Z YJU Fire (JOI20_ho_t5) C++14
6 / 100
 1000 ms 55440 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
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 ll base=N>>1;
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<<1)]+=(mid-l)*tag[id];
			sum[(id<<1)+1]+=(r-mid)*tag[id];
			tag[(id<<1)]+=tag[id];
			tag[(id<<1)+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<<1),l,mid,ql,qr,val);
		add((id<<1)+1,mid,r,ql,qr,val);
		sum[id]=sum[(id<<1)]+sum[(id<<1)+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<<1),l,mid,ql,qr)+ask((id<<1)+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+base)+seg2.ask(1,0,N,1,r+1+base);
}

void update(int ql,int qr,ll val){
	seg1.add(1,0,N,ql+base,N,val);
	seg2.add(1,0,N,qr+1+base,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 930 ms 53564 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 Execution timed out 1006 ms 55440 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 53776 KB Output is correct
2 Correct 874 ms 54008 KB Output is correct
3 Correct 880 ms 54544 KB Output is correct
4 Correct 877 ms 53648 KB Output is correct
5 Correct 887 ms 54032 KB Output is correct
6 Correct 874 ms 53904 KB Output is correct
7 Correct 881 ms 54304 KB Output is correct
8 Correct 890 ms 54032 KB Output is correct
9 Correct 882 ms 53776 KB Output is correct
10 Correct 870 ms 54244 KB Output is correct
11 Correct 888 ms 53904 KB Output is correct
12 Correct 890 ms 54032 KB Output is correct
13 Correct 895 ms 54288 KB Output is correct
14 Correct 878 ms 54208 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 -