oj.uz

Submission #518799

# Submission time Handle Problem Language Result Execution time Memory
518799 2022-01-24T16:59:46 Z HynDuf Fire (JOI20_ho_t5) C++11
13 / 100
 479 ms 162456 KB 
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; FOR(_, l, r) DB1(A, _); cerr << '\n';}
#define sz(x) ((int) (x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;

typedef pair<ll, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vl;
template<typename T>
struct FT {
	vector<T> fenw;
	FT() {}
	FT(int N) : fenw(N + 1, 0) {}
	void upd(int x, T v) {
		// case x < 1?
		assert(x > 0);
		for (; x < sz(fenw); x += x & -x) {
			fenw[x] += v;
		}
	}
	T query(int x) {
		// case x >= sz(fenw)?
		assert(x < sz(fenw));
		T ans = 0;
		for (; x > 0; x -= x & -x) ans += fenw[x];
		return ans;
	}
	T query(int l, int r) {
		return query(r) - query(l - 1);
	}
};
const int N = 2e5 + 2;
int n, q, ans[N], s[N];
viii qu[N];
vii upd_list[N][6]; // {v, pos}
FT<ll> fw[6];
// fw[0] ~ sum of v of open segments (to do: cur_time*sum_v - (0 - 1)*v) ~ all segments start at time 0
// fw[1] ~ sum of (left-1)*v of open segments (to do: pos*sum_v -(left - 1)*v)
// fw[2] ~ sum of (left-1)*v of closed segments
// fw[3] ~ sum of v of left closed segments
// fw[4] ~ sum of right*v of closed segments
// fw[5] ~ sum of v of right closed segments
void push_upd_events(int l, int r, int v)
{
	if (l > r) return;
	assert(l >= 1 && r <= 2 * n);
	upd_list[0][0].pb({v, l});
	upd_list[0][1].pb({(l - 1) * 1LL * v, l});
	int end_time = r - l + 1;
	upd_list[end_time][0].pb({-v, l});
	upd_list[end_time][1].pb({-(l - 1) * 1LL * v, l});
	upd_list[end_time][2].pb({(l - 1) * 1LL * v, l});
	upd_list[end_time][3].pb({v, l});
	upd_list[end_time][4].pb({r * 1LL * v, r});
	upd_list[end_time][5].pb({v, r});

}
void push_raw_upd_events(int l, int r, int t, int v)
{
	l += n, r += n;
	int L = l - t;
	push_upd_events(L, l - 1, -v);
	push_upd_events(L, r, v);
}
int D[N], top, right[N];
void build_upd_list()
{
	FOR(i, 0, 5) fw[i] = FT<ll> (2 * n);
	D[0] = n + 1;
	FORD(i, n, 1)
	{
		while (top && s[D[top]] < s[i]) 
		{
			push_raw_upd_events(D[top], right[D[top]], D[top] - i, -s[D[top]]);
			top--;
		}
		right[i] = D[top] - 1;
		push_raw_upd_events(i, right[i], 0, s[i]);
		D[++top] = i;
	}
}
ll cal(int pos, int cur_time)
{
	if (pos == 0) return 0;
	pos += n;
	ll res = 0;
	// open segments
	ll sum_v = fw[0].query(pos - cur_time);
	res += sum_v * (cur_time + 1);
	ll sum_left = fw[1].query(pos - cur_time + 1, pos);
	sum_v = fw[0].query(pos - cur_time + 1, pos);
	res += pos * sum_v - sum_left;
	// close segments
	sum_v = fw[3].query(pos);
	sum_left = fw[2].query(pos);
	res += pos * sum_v - sum_left;
	sum_v = fw[5].query(pos);
	ll sum_right = fw[4].query(pos);
	res += sum_right - pos * sum_v;
	return res;
}
int main()
{
#ifdef HynDuf
	freopen("inp.txt", "r", stdin);
#else
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
	cin >> n >> q;
	FOR(i, 1, n) cin >> s[i];
	FOR(i, 1, q)
	{
		int l, r, t;
		cin >> t >> l >> r;
		qu[t].pb({l, r, i});
	}
	build_upd_list();
	FOR(cur_time, 0, n)
	{
		FOR(i, 0, 5) for (ii &v : upd_list[cur_time][i]) fw[i].upd(v.S, v.F);
		for (auto &Q : qu[cur_time]) ans[Q[2]] = cal(Q[1], cur_time) - cal(Q[0] - 1, cur_time);
	}
	FOR(i, 1, q) cout << ans[i] << '\n';
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33104 KB Output is correct
2 Incorrect 16 ms 33360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33104 KB Output is correct
2 Incorrect 443 ms 146376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33104 KB Output is correct
2 Correct 439 ms 148104 KB Output is correct
3 Correct 424 ms 147220 KB Output is correct
4 Correct 457 ms 162456 KB Output is correct
5 Correct 460 ms 147788 KB Output is correct
6 Correct 479 ms 148296 KB Output is correct
7 Correct 428 ms 156836 KB Output is correct
8 Correct 449 ms 148092 KB Output is correct
9 Correct 444 ms 147932 KB Output is correct
10 Correct 403 ms 147164 KB Output is correct
11 Correct 458 ms 159968 KB Output is correct
12 Correct 438 ms 159072 KB Output is correct
13 Correct 474 ms 159568 KB Output is correct
14 Correct 442 ms 148428 KB Output is correct
15 Correct 444 ms 162340 KB Output is correct
16 Correct 432 ms 161216 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 115936 KB Output is correct
2 Correct 382 ms 117268 KB Output is correct
3 Correct 379 ms 122748 KB Output is correct
4 Correct 414 ms 124816 KB Output is correct
5 Correct 382 ms 122704 KB Output is correct
6 Correct 373 ms 117180 KB Output is correct
7 Correct 416 ms 125776 KB Output is correct
8 Correct 408 ms 123280 KB Output is correct
9 Correct 371 ms 123672 KB Output is correct
10 Correct 407 ms 117380 KB Output is correct
11 Correct 412 ms 118028 KB Output is correct
12 Correct 381 ms 121516 KB Output is correct
13 Correct 376 ms 117148 KB Output is correct
14 Correct 374 ms 121968 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33104 KB Output is correct
2 Incorrect 16 ms 33360 KB Output isn't correct
3 Halted 0 ms 0 KB -