| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1064610 |
2024-08-18T15:33:52 Z |
_8_8_ |
Fire (JOI20_ho_t5) |
C++17 |
|
1000 ms |
32324 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 12, MOD = (int)1e9 + 7;
int n,q,s[N];
struct fenw{
vector<ll> t;
void init(int n_) {
t.resize(n_+3);
}
void upd(int pos,ll val) {
while(pos <= n) {
t[pos] += val;
pos += (pos & -pos);
}
}
ll get(int i){
ll ret =0;
while(i) {
ret += t[i];
i -= i & -i;
}
return ret;
}
ll get(int l,int r) {
if(!l) return get(r);
return get(r) - get(l - 1);
}
};
fenw x,y;
ll t[N * 4], sum[N * 4], cmin[N * 4], cmax[N * 4], add[N * 4];
void assign(int v,ll val) {
add[v] += val;
cmin[v] += val;cmax[v] += val;
sum[v] += t[v] * val;
}
void push(int v) {
if(add[v]) {
assign(v + v,add[v]);
assign(v + v + 1,add[v]);
add[v] = 0;
}
}
void merge(int v) {
sum[v] = sum[v + v] + sum[v + v + 1];
cmin[v] = min(cmin[v + v],cmin[v + v + 1]);
cmax[v] = max(cmax[v + v],cmax[v + v + 1]);
t[v] = t[v + v] + t[v + v + 1];
}
void upd(int l,int r,int v = 1,int tl = 0,int tr = n ) {
if(l > r || tl > r || l > tr) return;
if(tl >= l && tr <= r) {
assign(v,1);
} else {
push(v);
int tm = (tl + tr) >> 1;
upd(l,r,v+v,tl,tm);
upd(l,r,v + v + 1,tm + 1,tr);
merge(v);
}
}
void upd1(int pos,ll val,int v = 1,int tl = 0,int tr = n) {
if(tl == tr) {
sum[v] = t[v] = val;
cmax[v] = cmin[v] = 1;
} else {
push(v);
int tm = (tl + tr) >> 1;
if(pos <= tm) upd1(pos,val,v+v,tl,tm);
else upd1(pos,val,v+v+1,tm+1,tr);
merge(v);
}
}
ll C[N];
ll get(int l,int r,int t_,int v = 1,int tl = 0,int tr = n) {
if(l > r || tl > r || l > tr) return 0;
if(tl >= l && tr <= r && tl == tr) {
ll cost = min((ll)t_,cmin[v]+C[tl]-1);
// cout << tl << ' ' << cost << '\n';
return cost * 1ll * t[v];
if(cmax[v] <= t_) {
return sum[v];
}
if(cmin[v] >= t_) {
// cout << tl << ' ' << tr << " " << cmin[v] << " " << t[v] << '\n';
return t[v] * 1ll * t_;
}
}
push(v);
int tm = (tl + tr) >> 1;
return get(l,r,t_,v+v,tl,tm) + get(l,r,t_,v+v+1,tm+1,tr);
}
ll find(int pos,int v = 1,int tl = 0,int tr = n) {
if(tl == tr) {
assert(cmax[v] == cmin[v]);
return cmax[v];
} else {
push(v);
int tm = (tl + tr) >> 1;
ll ret;
if(pos <= tm) ret = find(pos,v + v,tl,tm);
else ret = find(pos,v + v + 1,tm + 1,tr);
return ret;
}
}
ll ans[N],w[N],pref[N];
vector<array<int,2>> qr[N];
void test() {
cin >> n >> q;
for(int i = 1;i <= n;i++) {
cin >> s[i];
pref[i] = pref[i - 1] + s[i];
}
for(int i = 1;i <= q;i++) {
int l,r,t_;
cin >> t_ >> l >> r;
ans[i] += pref[r] - pref[l - 1];
qr[r].push_back({t_,i});
qr[l - 1].push_back({t_,i + q});
}
x.init(n);
y.init(n);
vector<int> st;
ll er = 0;
for(int i = 1;i <= n;i++) {
while(!st.empty() && s[st.back()] < s[i]) {
int j = st.back(),id = (int)st.size() - 1;
int c = find(id);
x.upd(c,w[j]);
y.upd(c,c*1ll*w[j]);
st.pop_back();
}
if((int)st.size()) {
w[i] = s[st.back()] - s[i];
C[(int)st.size()] = i - st.back();
er += (C[(int)st.size()]-1)* 1ll * w[i];
}
upd(0,(int)st.size() - 1);
upd1((int)st.size(),w[i]);
st.push_back(i);
for(auto [t_,id]:qr[i]) {
ans[id] += get(0,(int)st.size()-1,t_) + x.get(t_ + 1,n) * 1ll * t_ + y.get(0,t_) - er;
}
}
for(int i = 1;i <= q;i++) {
cout << ans[i] - ans[i + q] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 2 |
Incorrect |
243 ms |
32324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 2 |
Incorrect |
249 ms |
31892 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1006 ms |
28712 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
9820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
