| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 541122 |
2022-03-22T09:51:06 Z |
8e7 |
Dungeon 3 (JOI21_ho_t5) |
C++17 |
|
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 |
- |
