| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 754944 |
2023-06-09T03:13:53 Z |
pcc |
Fire (JOI20_ho_t5) |
C++14 |
|
1000 ms |
117440 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define int ll
const ll mxn = 4e5+10;
struct Seg{
pll segtree[mxn*4];
Seg(){
for(auto &i:segtree)i = {0,0};
}
void modify(int now,int l,int r,int s,int e,ll v){
if(l>=s&&e>=r){
segtree[now].sc += v;
return;
}
int mid = (l+r)>>1;
if(mid>=s)modify(now*2+1,l,mid,s,e,v);
if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
segtree[now].fs =
segtree[now*2+1].fs+segtree[now*2+1].sc*(mid-l+1)+segtree[now*2+2].fs+segtree[now*2+2].sc*(r-mid);
}
ll getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r){
return segtree[now].fs+segtree[now].sc*(r-l+1);
}
int mid = (l+r)>>1;
if(mid>=e)return getval(now*2+1,l,mid,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1);
else if(mid<s)return getval(now*2+2,mid+1,r,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1);
else return getval(now*2+1,l,mid,s,e)+getval(now*2+2,mid+1,r,s,e)+segtree[now].sc*(min(e,r)-max(s,l)+1);
}
};
Seg seg1,seg2;
vector<pll> op[mxn];
ll arr[mxn];
ll n,q;
vector<tuple<ll,ll,ll>> req[mxn];
pll range[mxn];
ll ans[mxn];
ll sh = mxn>>1;
void addtri(int r,int c,ll val){
op[c].push_back({r,val});
}
void add(int now,int h,int w){
//cout<<now<<":"<<h<<' '<<w<<endl;
addtri(now,0,arr[now]);
addtri(now,h,-arr[now]);
addtri(now+w,w,-arr[now]);
addtri(now+w,h+w,arr[now]);
return;
}
int32_t main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i = 1;i<=n;i++){
cin>>arr[i];
}
for(int i = 1;i<=q;i++){
ll t,l,r;
cin>>t>>l>>r;
req[t].push_back(make_tuple(1LL*i,l,r));
}
arr[0] = arr[n+1] = 1e18;
deque<int> dq;
dq.push_back(0);
for(int i = 1;i<=n;i++){
while(arr[dq.back()]<=arr[i])dq.pop_back();
range[i].fs = dq.back();
dq.push_back(i);
}
dq.clear();
dq.push_back(n+1);
for(int i = n;i>=1;i--){
while(arr[dq.back()]<arr[i])dq.pop_back();
range[i].sc = dq.back();
dq.push_back(i);
//cout<<i<<":"<<range[i].fs<<' '<<range[i].sc<<'\n';
}
for(int i = 1;i<=n;i++){
if(range[i].fs == 0)range[i].fs = n+1;
else range[i].fs = i-range[i].fs;
range[i].sc = range[i].sc-i;
add(i,range[i].fs,range[i].sc);
}
for(int i = 0;i<=n;i++){
for(auto &j:op[i]){
seg1.modify(0,1,mxn,j.fs,mxn,j.sc);
seg2.modify(0,1,mxn,sh+j.fs+1,mxn,-j.sc);
}
for(auto &j:req[i]){
ans[get<0>(j)] =
seg1.getval(0,1,mxn,get<1>(j),get<2>(j))+seg2.getval(0,1,mxn,sh+get<1>(j),sh+get<2>(j));
}
for(int i = 1;i<=n;i++)cout<<seg1.getval(0,1,mxn,i,i)<<' ';cout<<endl;
for(int i = 1;i<=n;i++)cout<<seg2.getval(0,1,mxn,sh+i,sh+i)<<' ';cout<<endl;
/*
*/
sh--;
}
for(int i = 1;i<=q;i++)cout<<ans[i]<<'\n';
return 0;
}
Compilation message
ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:102:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
102 | for(int i = 1;i<=n;i++)cout<<seg1.getval(0,1,mxn,i,i)<<' ';cout<<endl;
| ^~~
ho_t5.cpp:102:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
102 | for(int i = 1;i<=n;i++)cout<<seg1.getval(0,1,mxn,i,i)<<' ';cout<<endl;
| ^~~~
ho_t5.cpp:103:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
103 | for(int i = 1;i<=n;i++)cout<<seg2.getval(0,1,mxn,sh+i,sh+i)<<' ';cout<<endl;
| ^~~
ho_t5.cpp:103:69: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
103 | for(int i = 1;i<=n;i++)cout<<seg2.getval(0,1,mxn,sh+i,sh+i)<<' ';cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
69204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
69204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
69204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
117440 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
69204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
