oj.uz

Submission #349899

# Submission time Handle Problem Language Result Execution time Memory
349899 2021-01-18T16:12:10 Z YJU Fire (JOI20_ho_t5) C++14
100 / 100
 968 ms 67432 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
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],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<<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
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 18 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 25324 KB Output is correct
13 Correct 18 ms 25324 KB Output is correct
14 Correct 18 ms 25344 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 18 ms 25324 KB Output is correct
19 Correct 18 ms 25324 KB Output is correct
20 Correct 18 ms 25344 KB Output is correct
21 Correct 18 ms 25324 KB Output is correct
22 Correct 18 ms 25324 KB Output is correct
23 Correct 18 ms 25344 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 25324 KB Output is correct
31 Correct 18 ms 25324 KB Output is correct
32 Correct 19 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 851 ms 56628 KB Output is correct
3 Correct 823 ms 56408 KB Output is correct
4 Correct 884 ms 57304 KB Output is correct
5 Correct 863 ms 58968 KB Output is correct
6 Correct 861 ms 57032 KB Output is correct
7 Correct 871 ms 56796 KB Output is correct
8 Correct 882 ms 59992 KB Output is correct
9 Correct 876 ms 58384 KB Output is correct
10 Correct 844 ms 56280 KB Output is correct
11 Correct 858 ms 58456 KB Output is correct
12 Correct 834 ms 57048 KB Output is correct
13 Correct 877 ms 58840 KB Output is correct
14 Correct 855 ms 58968 KB Output is correct
15 Correct 872 ms 58800 KB Output is correct
16 Correct 876 ms 57432 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 932 ms 58100 KB Output is correct
3 Correct 925 ms 57300 KB Output is correct
4 Correct 929 ms 59756 KB Output is correct
5 Correct 907 ms 58128 KB Output is correct
6 Correct 908 ms 58420 KB Output is correct
7 Correct 906 ms 59280 KB Output is correct
8 Correct 909 ms 57744 KB Output is correct
9 Correct 923 ms 57796 KB Output is correct
10 Correct 907 ms 57648 KB Output is correct
11 Correct 931 ms 59792 KB Output is correct
12 Correct 913 ms 59664 KB Output is correct
13 Correct 934 ms 60816 KB Output is correct
14 Correct 914 ms 57488 KB Output is correct
15 Correct 927 ms 61072 KB Output is correct
16 Correct 905 ms 60628 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 56720 KB Output is correct
2 Correct 828 ms 57104 KB Output is correct
3 Correct 843 ms 57652 KB Output is correct
4 Correct 843 ms 56592 KB Output is correct
5 Correct 838 ms 56980 KB Output is correct
6 Correct 834 ms 56976 KB Output is correct
7 Correct 838 ms 57616 KB Output is correct
8 Correct 846 ms 57392 KB Output is correct
9 Correct 838 ms 56976 KB Output is correct
10 Correct 844 ms 57392 KB Output is correct
11 Correct 846 ms 56976 KB Output is correct
12 Correct 845 ms 57104 KB Output is correct
13 Correct 842 ms 56976 KB Output is correct
14 Correct 841 ms 57360 KB Output is correct

Subtask #5
80.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 18 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 25324 KB Output is correct
13 Correct 18 ms 25324 KB Output is correct
14 Correct 18 ms 25344 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 18 ms 25324 KB Output is correct
19 Correct 18 ms 25324 KB Output is correct
20 Correct 18 ms 25344 KB Output is correct
21 Correct 18 ms 25324 KB Output is correct
22 Correct 18 ms 25324 KB Output is correct
23 Correct 18 ms 25344 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 25324 KB Output is correct
31 Correct 18 ms 25324 KB Output is correct
32 Correct 19 ms 25324 KB Output is correct
33 Correct 936 ms 59032 KB Output is correct
34 Correct 951 ms 64784 KB Output is correct
35 Correct 947 ms 67432 KB Output is correct
36 Correct 939 ms 64528 KB Output is correct
37 Correct 927 ms 64384 KB Output is correct
38 Correct 954 ms 65680 KB Output is correct
39 Correct 935 ms 64272 KB Output is correct
40 Correct 944 ms 64036 KB Output is correct
41 Correct 925 ms 66064 KB Output is correct
42 Correct 951 ms 64540 KB Output is correct
43 Correct 878 ms 67144 KB Output is correct
44 Correct 873 ms 65936 KB Output is correct
45 Correct 859 ms 63888 KB Output is correct
46 Correct 867 ms 65680 KB Output is correct
47 Correct 853 ms 63848 KB Output is correct
48 Correct 852 ms 63376 KB Output is correct
49 Correct 859 ms 64212 KB Output is correct
50 Correct 875 ms 66320 KB Output is correct
51 Correct 871 ms 66192 KB Output is correct
52 Correct 882 ms 64252 KB Output is correct
53 Correct 876 ms 64272 KB Output is correct
54 Correct 968 ms 63888 KB Output is correct
55 Correct 948 ms 64784 KB Output is correct
56 Correct 964 ms 65040 KB Output is correct
57 Correct 949 ms 63504 KB Output is correct
58 Correct 959 ms 65680 KB Output is correct
59 Correct 851 ms 56628 KB Output is correct
60 Correct 823 ms 56408 KB Output is correct
61 Correct 884 ms 57304 KB Output is correct
62 Correct 863 ms 58968 KB Output is correct
63 Correct 861 ms 57032 KB Output is correct
64 Correct 871 ms 56796 KB Output is correct
65 Correct 882 ms 59992 KB Output is correct
66 Correct 876 ms 58384 KB Output is correct
67 Correct 844 ms 56280 KB Output is correct
68 Correct 858 ms 58456 KB Output is correct
69 Correct 834 ms 57048 KB Output is correct
70 Correct 877 ms 58840 KB Output is correct
71 Correct 855 ms 58968 KB Output is correct
72 Correct 872 ms 58800 KB Output is correct
73 Correct 876 ms 57432 KB Output is correct
74 Correct 932 ms 58100 KB Output is correct
75 Correct 925 ms 57300 KB Output is correct
76 Correct 929 ms 59756 KB Output is correct
77 Correct 907 ms 58128 KB Output is correct
78 Correct 908 ms 58420 KB Output is correct
79 Correct 906 ms 59280 KB Output is correct
80 Correct 909 ms 57744 KB Output is correct
81 Correct 923 ms 57796 KB Output is correct
82 Correct 907 ms 57648 KB Output is correct
83 Correct 931 ms 59792 KB Output is correct
84 Correct 913 ms 59664 KB Output is correct
85 Correct 934 ms 60816 KB Output is correct
86 Correct 914 ms 57488 KB Output is correct
87 Correct 927 ms 61072 KB Output is correct
88 Correct 905 ms 60628 KB Output is correct
89 Correct 832 ms 56720 KB Output is correct
90 Correct 828 ms 57104 KB Output is correct
91 Correct 843 ms 57652 KB Output is correct
92 Correct 843 ms 56592 KB Output is correct
93 Correct 838 ms 56980 KB Output is correct
94 Correct 834 ms 56976 KB Output is correct
95 Correct 838 ms 57616 KB Output is correct
96 Correct 846 ms 57392 KB Output is correct
97 Correct 838 ms 56976 KB Output is correct
98 Correct 844 ms 57392 KB Output is correct
99 Correct 846 ms 56976 KB Output is correct
100 Correct 845 ms 57104 KB Output is correct
101 Correct 842 ms 56976 KB Output is correct
102 Correct 841 ms 57360 KB Output is correct