oj.uz

Submission #700994

# Submission time Handle Problem Language Result Execution time Memory
700994 2023-02-19T15:55:58 Z myrcella Fire (JOI20_ho_t5) C++17
0 / 100
 210 ms 38904 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 4e5+10;

struct rurq{
	ll tree1[maxn],tree2[maxn];
	void update(int l,int r,int val) {
		int pos = r+1;
		while (pos<maxn) {
			tree1[pos]-=val;
			tree2[pos]-=r*val;
			pos+=lowbit(pos);
		}
		pos = l;
		while (pos<maxn) {
			tree1[pos]+=val;
			tree2[pos]+=(l-1)*val;
			pos+=lowbit(pos);
		}
	}
	ll query(int pos) {
		ll ret = 0;
		int tmp = pos;
		while (pos) {
			ret += tree1[pos]*tmp;
			ret -= tree2[pos];
			pos-=lowbit(pos);
		}
		return ret;
	}
	ll query(int l,int r) {
		return query(r)-query(l-1);
	}
}vert,diag;

int n,m;
int a[maxn];
int lt[maxn],rt[maxn];
ll ans[maxn];
vector <pair<pii,int>> q[maxn];
vector <pair<pii,int>> upd[maxn];

void tri(int l,int r,int val) {
	if (l>r) return;
	diag.update(l+n,n+n,val);
	vert.update(r+1+n,n+n,-val);
	if (r-l+1<=n) upd[r-l+1].pb({{l,r},val});
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	rep(i,0,n) cin>>a[i];
	rep(i,0,m) {
		int t,l,r;
		cin>>t>>l>>r;
		l--,r--;
		q[t].pb({{l,r},i});
	}
	stack<int> s;
	rep(i,0,n) {
		while (!s.empty() and a[s.top()]<a[i]) s.pop();
		if (s.empty()) lt[i] = i-n;
		else lt[i] = s.top();
		s.push(i);
	}
	while (!s.empty()) s.pop();
	for (int i =n-1;i>=0;i--) {
		while (!s.empty() and a[s.top()]<a[i]) s.pop();
		if(s.empty()) rt[i] = n;
		else rt[i] = s.top();
		s.push(i);
	}
	rep(i,0,n) {
		tri(lt[i]+1,rt[i]-1,a[i]);
		tri(lt[i]+1,i-1,-a[i]);
		tri(i+1,rt[i]-1,-a[i]);
	}
	rep(i,1,n+1) {
		for (auto j:upd[i]) {
			int l = j.fi.fi,r = j.fi.se, val = j.se;
			diag.update(l+n,n+n,-val);
			vert.update(r+1+n,n+n,val);
		}
		for (auto j:q[i]) {
			ans[j.se] = vert.query(j.fi.fi+n,j.fi.se+n) + diag.query(j.fi.fi-i+n,j.fi.se-i+n);
		}
	}
	rep(i,0,m) cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 38904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 38904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 38904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 38340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 38904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -