oj.uz

답안 #349891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349891 2021-01-18T15:53:57 Z YJU Fire (JOI20_ho_t5) C++14
7 / 100
 1000 ms 60336 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]){
			L[i]=stk[sz];
			R[stk[sz]]=i;
			--sz;
		}
		L[i]=(a[L[i]]==a[i]?L[i]:(sz==0?i-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){
		//cout<<i<<"\n";
		for(auto k:work[i]){
			//cout<<k.X.X<<" "<<k.X.Y<<" "<<k.Y<<"\n";
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Correct 19 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 25196 KB Output is correct
7 Correct 18 ms 25324 KB Output is correct
8 Correct 21 ms 25324 KB Output is correct
9 Correct 20 ms 25264 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 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 18 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 18 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 25324 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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Correct 914 ms 56840 KB Output is correct
3 Correct 893 ms 56408 KB Output is correct
4 Correct 972 ms 57816 KB Output is correct
5 Correct 938 ms 59096 KB Output is correct
6 Correct 947 ms 57432 KB Output is correct
7 Correct 937 ms 57176 KB Output is correct
8 Correct 950 ms 60336 KB Output is correct
9 Correct 948 ms 58456 KB Output is correct
10 Correct 912 ms 56408 KB Output is correct
11 Correct 935 ms 58712 KB Output is correct
12 Correct 903 ms 56908 KB Output is correct
13 Correct 958 ms 59096 KB Output is correct
14 Correct 931 ms 59096 KB Output is correct
15 Correct 933 ms 58968 KB Output is correct
16 Correct 943 ms 57432 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Execution timed out 1004 ms 58528 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 875 ms 53580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25196 KB Output is correct
2 Correct 19 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 25196 KB Output is correct
7 Correct 18 ms 25324 KB Output is correct
8 Correct 21 ms 25324 KB Output is correct
9 Correct 20 ms 25264 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 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 18 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 18 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 25324 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 1018 ms 59280 KB Time limit exceeded
34 Halted 0 ms 0 KB -