Submission #541122

# Submission time Handle Problem Language Result Execution time Memory
541122 2022-03-22T09:51:06 Z 8e7 Dungeon 3 (JOI21_ho_t5) C++17
31 / 100
608 ms 196028 KB
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct sparse_segtree{
	struct node{
		ll m, tag, k;
		node *lef, *rig;
		node(){m = tag = k = 0, lef = rig = NULL;}
		node(ll a, ll b, ll c){m = a, tag = b, k = c;}
	};
	node *root = new node();	
	void add(node * &x) {
		if (x == NULL) {
			x = new node();
		}
	}
	ll calc(int l, int r, ll m) {
		return m * (l + r - 1) * (r - l) / 2;
	}
	void modify(node *cur, ll l, ll r, ll ql, ll qr, ll m, ll k) {
		if (cur == root) debug(ql, qr, m, k);
		if (r <= l || qr <= l || ql >= r) return;
		if (ql <= l && qr >= r) {
			cur->m += m;
			cur->tag += k;	
			return;
		}
		ll mid = (l + r) / 2;	
		add(cur->lef), add(cur->rig); 
		modify(cur->lef, l, mid, ql, qr, m, k);	
		modify(cur->rig, mid, r, ql, qr, m, k);
		cur->k = cur->lef->k + cur->rig->k + calc(l, m, cur->lef->m) + calc(m, r, cur->rig->m) + 
			cur->lef->tag + cur->rig->tag;
	}	
	ll query(node *cur, ll l, ll r, int x) {
		if (r <= l || x < l || x >= r) return 0;
		if (r - l == 1) return calc(l, r, cur->m) + cur->k + cur->tag;
		ll m = (l + r) / 2;
		ll lef = (cur->lef ? query(cur->lef, l, m, x) : 0);
		ll rig = (cur->rig ? query(cur->rig, m, r, x) : 0);
		return (x < m ? lef : rig) + cur->tag + cur->m * x;
	}
} tr;

struct segtree{
	ll seg[4*maxn];
	int type = 0;
	void init(int cur, int l, int r, ll a[]) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = a[l];
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, a), init(cur*2+1, m, r, a);
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
		if (type == 1) seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	ll query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return (type ? 0 : inf);
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		ll vl = query(cur*2, l, m, ql, qr), vr = query(cur*2+1, m, r, ql, qr);
		if (type) return max(vl, vr);
		else return min(vl,vr);
	}
} ma, mb;
struct query{
	int c, u, id;	
	query(){c = u = id = 0;}
	query(int b, int p, int q){c = b, u = p, id = q;}
};
ll a[maxn], b[maxn], pref[maxn];
int prv[maxn];
vector<query> que[maxn];
ll ans[maxn];
int main() {
	io
	int n, m;
	cin >> n >> m;	
	for (int i = 1;i<= n;i++) cin >> a[i], pref[i] = a[i] + pref[i-1];
	for (int i = 1;i <= n;i++) cin >> b[i];
	ma.type = 1;
	ma.init(1, 1, n+1, a);
	mb.init(1, 1, n+1, b);
	stack<int> stk;		
	for (int i = 0;i < m;i++) {
		int s, t, u;
		cin >> s >> t >> u;
		if (ma.query(1, 1, n+1, s, t) > u) {
			ans[i] = -1;
		} else {
			que[s].push_back(query(1, u, i));
		}
		//que[t+1].push_back(query(-1, u, i));
	}	
	const int mu = 100000005;
	
	for (int i = n;i >= 1;i--) {
		while (stk.size() && b[i] < b[stk.top()]) {
			int cur = stk.top();
			stk.pop();
			ll pnt = pref[cur-1] - pref[i-1] + 1;
			if (pnt < mu) {
				tr.modify(tr.root, 0, mu, pnt, mu, -b[cur], -b[cur] * (1 - pnt));
				ll len = pref[prv[cur]-1] - pref[i-1] + 1;
				tr.modify(tr.root, 0, mu, len, mu, b[cur], b[cur] * (1 - len));
			}
		}	
		prv[i] = (stk.size() ? stk.top() : n+1);
		stk.push(i);
		tr.modify(tr.root, 0, mu, 0, mu, b[i], 0); //ok
		ll len = pref[prv[i]-1] - pref[i-1] + 1;
		tr.modify(tr.root, 0, mu, len, mu, -b[i], -b[i] * (1 - len)); //ok

		for (auto q:que[i]) {
			ans[q.id] += q.c * tr.query(tr.root, 0, mu, q.u);	
		}
		/*
		for (int j = 1;j <= 10;j++) {
			cout << tr.query(tr.root, 0, mu, j) << " ";
		}
		cout << "\n";
		*/
	}	
	for (int i = 0;i < m;i++) cout << ans[i] << "\n";
}
/*
5 4
3 4 1 2 2
2 5 1 2 1
3 6 1
3 6 2
3 6 3

3 4
1 2 2
1 2 1
1 4 1
1 4 2
1 4 3
1 4 4
*/

Compilation message

Main.cpp: In member function 'void sparse_segtree::modify(sparse_segtree::node*, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
Main.cpp:40:20: note: in expansion of macro 'debug'
   40 |   if (cur == root) debug(ql, qr, m, k);
      |                    ^~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9172 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 29900 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 608 ms 62676 KB Output is correct
2 Correct 354 ms 39980 KB Output is correct
3 Correct 319 ms 46256 KB Output is correct
4 Correct 535 ms 92176 KB Output is correct
5 Correct 304 ms 61608 KB Output is correct
6 Correct 347 ms 39932 KB Output is correct
7 Correct 392 ms 34612 KB Output is correct
8 Correct 265 ms 29828 KB Output is correct
9 Correct 248 ms 29520 KB Output is correct
10 Correct 476 ms 196028 KB Output is correct
11 Correct 318 ms 45952 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9172 KB Output isn't correct
2 Halted 0 ms 0 KB -