oj.uz

Submission #839274

# Submission time Handle Problem Language Result Execution time Memory
839274 2023-08-29T13:40:42 Z denniskim Fire (JOI20_ho_t5) C++17
1 / 100
 1000 ms 151464 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll T, L, R, num;
	
	bool operator < (const gujo &xx) const
	{
		return T < xx.T;
	}
};

struct gujo2
{
	ll T, gap, typ, X;
	
	bool operator < (const gujo2 &xx) const
	{
		return T < xx.T;
	}
};

ll n, q;
ll a[200010];
gujo Q[200010];
ll Lidx[200010], Ridx[200010];
ll h[200010], w[200010];
vector<gujo2> vec2;
ll ans[200010];

struct lazysegtree
{
	ll seg[4000010];
	ll lazy[4000010];
	
	void prop(ll no, ll s, ll e)
	{
		if(lazy[no])
		{
			seg[no] += lazy[no] * (e - s + 1);
			
			if(s != e)
			{
				lazy[no << 1] += lazy[no];
				lazy[no << 1 | 1] += lazy[no];
			}
			
			lazy[no] = 0;
		}
	}
	
	void update(ll no, ll s, ll e, ll l, ll r, ll v)
	{
		prop(no, s, e);
		
		if(e < l || r < s)
			return;
		
		if(l <= s && e <= r)
		{
			seg[no] += v * (e - s + 1);
			
			if(s != e)
			{
				lazy[no << 1] += v;
				lazy[no << 1 | 1] += v;
			}
			
			return;
		}
		
		update(no << 1, s, (s + e) >> 1, l, r, v);
		update(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r, v);
		
		seg[no] = seg[no << 1] + seg[no << 1 | 1];
	}
	
	ll query(ll no, ll s, ll e, ll l, ll r)
	{
		prop(no, s, e);
		
		if(e < l || r < s)
			return 0;
		
		if(l <= s && e <= r)
			return seg[no];
		
		return query(no << 1, s, (s + e) >> 1, l, r) + query(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r);
	}
}segt1, segt2;

void LR(void)
{
	stack<ll> stk;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		while(!stk.empty() && a[stk.top()] <= a[i])
			stk.pop();
		
		if(!stk.empty())
			Lidx[i] = stk.top();
		
		stk.push(i);
	}
	
	while(!stk.empty())
		stk.pop();
	
	for(ll i = n ; i >= 1 ; i--)
	{
		while(!stk.empty() && a[stk.top()] < a[i])
			stk.pop();
		
		if(!stk.empty())
			Ridx[i] = stk.top();
		
		stk.push(i);
	}
}

void diag(ll X, ll S, ll E, ll gp)
{
	vec2.push_back({S, X, 1, gp});
	vec2.push_back({E + 1, X, -1, -gp});
}

void rect(ll X, ll S, ll E, ll gp)
{
	vec2.push_back({S, X, 2, gp});
	vec2.push_back({E + 1, X, -2, -gp});
}

void tri(ll idx, ll len, ll S, ll E, ll gp)
{
	diag(S - idx, S, E, gp);
	rect(idx + len, S, E, -gp);
}

int main(void)
{
	//fastio
	
	cin >> n >> q;
	
	for(ll i = 1 ; i <= n ; i++)
		cin >> a[i];
	
	for(ll i = 1 ; i <= q ; i++)
	{
		cin >> Q[i].T >> Q[i].L >> Q[i].R;
		Q[i].num = i;
	}
	
	sort(Q + 1, Q + 1 + q);
	
	LR();
	
	for(ll i = 1 ; i <= n ; i++)
	{
		if(!Lidx[i])
			h[i] = n + 1;
		else
			h[i] = i - Lidx[i];
		
		if(!Ridx[i])
			w[i] = n - i + 1;
		else
			w[i] = Ridx[i] - i;
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		tri(i - h[i] + 1, h[i] + w[i] - 1, 0, h[i] + w[i] - 2, a[i]);
		tri(i - h[i] + 1, h[i] - 1, 0, h[i] - 2, -a[i]);
		tri(i + 1, w[i] - 1, 0, w[i] - 2, -a[i]);
	}
	
	sort(vec2.begin(), vec2.end());
	
	ll p = 0;
	
	for(ll i = 1 ; i <= q ; i++)
	{
		while(p < (ll)vec2.size() && vec2[p].T <= Q[i].T)
		{
			if(abs(vec2[p].typ) == 1)
				segt1.update(1, 0, 4 * n, 0, vec2[p].gap + n, vec2[p].X);
			else
				segt2.update(1, 0, 4 * n, vec2[p].gap, 4 * n, vec2[p].X);
			
			p++;
		}
		
		ans[Q[i].num] = segt1.query(1, 0, 4 * n, Q[i].T - Q[i].R + n, Q[i].T - Q[i].L + n);
		ans[Q[i].num] += segt2.query(1, 0, 4 * n, Q[i].L, Q[i].R);
	}
	
	for(ll i = 1 ; i <= q ; i++)
		cout << ans[i] en;
	
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1038 ms 151112 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 984 ms 151144 KB Output is correct
3 Correct 936 ms 150824 KB Output is correct
4 Execution timed out 1077 ms 151464 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 149488 KB Output is correct
2 Correct 977 ms 149400 KB Output is correct
3 Correct 991 ms 149828 KB Output is correct
4 Correct 913 ms 149700 KB Output is correct
5 Correct 961 ms 149560 KB Output is correct
6 Correct 957 ms 149592 KB Output is correct
7 Correct 984 ms 149640 KB Output is correct
8 Correct 969 ms 149684 KB Output is correct
9 Correct 981 ms 149624 KB Output is correct
10 Correct 964 ms 149536 KB Output is correct
11 Correct 957 ms 149804 KB Output is correct
12 Correct 956 ms 149724 KB Output is correct
13 Execution timed out 1008 ms 149656 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 568 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 2 ms 596 KB Output is correct
33 Execution timed out 1038 ms 151112 KB Time limit exceeded
34 Halted 0 ms 0 KB -