oj.uz

Submission #349894

# Submission time Handle Problem Language Result Execution time Memory
349894 2021-01-18T16:02:41 Z YJU Fire (JOI20_ho_t5) C++14
20 / 100
 1000 ms 66460 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 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],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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Correct 18 ms 25324 KB Output is correct
3 Correct 18 ms 25324 KB Output is correct
4 Correct 18 ms 25324 KB Output is correct
5 Correct 18 ms 25324 KB Output is correct
6 Correct 18 ms 25324 KB Output is correct
7 Correct 18 ms 25324 KB Output is correct
8 Correct 18 ms 25324 KB Output is correct
9 Correct 19 ms 25324 KB Output is correct
10 Correct 18 ms 25324 KB Output is correct
11 Correct 18 ms 25324 KB Output is correct
12 Correct 18 ms 25340 KB Output is correct
13 Correct 18 ms 25324 KB Output is correct
14 Correct 18 ms 25324 KB Output is correct
15 Correct 18 ms 25324 KB Output is correct
16 Correct 18 ms 25324 KB Output is correct
17 Correct 18 ms 25324 KB Output is correct
18 Correct 19 ms 25324 KB Output is correct
19 Correct 18 ms 25324 KB Output is correct
20 Correct 18 ms 25324 KB Output is correct
21 Correct 18 ms 25324 KB Output is correct
22 Correct 18 ms 25324 KB Output is correct
23 Correct 21 ms 25324 KB Output is correct
24 Correct 18 ms 25324 KB Output is correct
25 Correct 18 ms 25324 KB Output is correct
26 Correct 18 ms 25324 KB Output is correct
27 Correct 18 ms 25324 KB Output is correct
28 Correct 18 ms 25324 KB Output is correct
29 Correct 18 ms 25324 KB Output is correct
30 Correct 18 ms 25316 KB Output is correct
31 Correct 18 ms 25324 KB Output is correct
32 Correct 18 ms 25324 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Correct 911 ms 56664 KB Output is correct
3 Correct 898 ms 56432 KB Output is correct
4 Correct 928 ms 57176 KB Output is correct
5 Correct 909 ms 58968 KB Output is correct
6 Correct 933 ms 57196 KB Output is correct
7 Correct 930 ms 56920 KB Output is correct
8 Correct 941 ms 60096 KB Output is correct
9 Correct 942 ms 58456 KB Output is correct
10 Correct 910 ms 56460 KB Output is correct
11 Correct 938 ms 58328 KB Output is correct
12 Correct 893 ms 57148 KB Output is correct
13 Correct 941 ms 59096 KB Output is correct
14 Correct 913 ms 58968 KB Output is correct
15 Correct 928 ms 58760 KB Output is correct
16 Correct 954 ms 57304 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Correct 974 ms 58128 KB Output is correct
3 Correct 957 ms 57324 KB Output is correct
4 Correct 993 ms 60048 KB Output is correct
5 Correct 961 ms 63284 KB Output is correct
6 Correct 973 ms 63760 KB Output is correct
7 Correct 970 ms 65040 KB Output is correct
8 Correct 986 ms 63300 KB Output is correct
9 Correct 964 ms 63376 KB Output is correct
10 Correct 950 ms 62992 KB Output is correct
11 Correct 986 ms 65448 KB Output is correct
12 Correct 969 ms 65168 KB Output is correct
13 Correct 991 ms 66448 KB Output is correct
14 Correct 971 ms 63120 KB Output is correct
15 Correct 974 ms 66460 KB Output is correct
16 Correct 976 ms 66064 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 56692 KB Output is correct
2 Correct 867 ms 61328 KB Output is correct
3 Correct 897 ms 61968 KB Output is correct
4 Correct 886 ms 60944 KB Output is correct
5 Correct 871 ms 61252 KB Output is correct
6 Correct 867 ms 61216 KB Output is correct
7 Correct 877 ms 61828 KB Output is correct
8 Correct 883 ms 61428 KB Output is correct
9 Correct 871 ms 61072 KB Output is correct
10 Correct 867 ms 61584 KB Output is correct
11 Correct 888 ms 61496 KB Output is correct
12 Correct 884 ms 61192 KB Output is correct
13 Correct 875 ms 61200 KB Output is correct
14 Correct 883 ms 61456 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 Correct 18 ms 25324 KB Output is correct
3 Correct 18 ms 25324 KB Output is correct
4 Correct 18 ms 25324 KB Output is correct
5 Correct 18 ms 25324 KB Output is correct
6 Correct 18 ms 25324 KB Output is correct
7 Correct 18 ms 25324 KB Output is correct
8 Correct 18 ms 25324 KB Output is correct
9 Correct 19 ms 25324 KB Output is correct
10 Correct 18 ms 25324 KB Output is correct
11 Correct 18 ms 25324 KB Output is correct
12 Correct 18 ms 25340 KB Output is correct
13 Correct 18 ms 25324 KB Output is correct
14 Correct 18 ms 25324 KB Output is correct
15 Correct 18 ms 25324 KB Output is correct
16 Correct 18 ms 25324 KB Output is correct
17 Correct 18 ms 25324 KB Output is correct
18 Correct 19 ms 25324 KB Output is correct
19 Correct 18 ms 25324 KB Output is correct
20 Correct 18 ms 25324 KB Output is correct
21 Correct 18 ms 25324 KB Output is correct
22 Correct 18 ms 25324 KB Output is correct
23 Correct 21 ms 25324 KB Output is correct
24 Correct 18 ms 25324 KB Output is correct
25 Correct 18 ms 25324 KB Output is correct
26 Correct 18 ms 25324 KB Output is correct
27 Correct 18 ms 25324 KB Output is correct
28 Correct 18 ms 25324 KB Output is correct
29 Correct 18 ms 25324 KB Output is correct
30 Correct 18 ms 25316 KB Output is correct
31 Correct 18 ms 25324 KB Output is correct
32 Correct 18 ms 25324 KB Output is correct
33 Execution timed out 1004 ms 59024 KB Time limit exceeded
34 Halted 0 ms 0 KB -