Submission #203134

#TimeUsernameProblemLanguageResultExecution timeMemory
203134gs18115Fire (JOI20_ho_t5)C++14
100 / 100
469 ms82804 KiB
#include<iostream> #include<vector> #include<algorithm> #define ep emplace #define eb emplace_back #define fi first #define se second #define all(x) (x).begin(),(x).end() #define semicolon ; #define ryan bear using namespace std; typedef long long ll; typedef pair<int,int>pi; typedef pair<ll,ll>pl; const int inf=1e9+7; const ll INF=1e18; struct fen { ll a[400010],b[400010]; fen(){} inline void init() { fill(a,a+400010,0); fill(b,b+400010,0); return; } inline void fi(int x,ll p) { for(int i=x+1;i<400010;i+=i&-i) a[i]+=p; p*=1-x; for(int i=x+1;i<400010;i+=i&-i) b[i]+=p; return; } inline ll fq(int x) { ll as=0,bs=0; for(int i=x+1;i>0;i=i&i-1) as+=a[i],bs+=b[i]; return as*x+bs; } inline ll fq(int l,int r) { return fq(r)-fq(l-1); } }ft1,ft2; struct seg { ll t[800010]; seg(){} inline void init() { fill(t,t+800010,-INF); return; } void si(int n,int s,int e,int x,ll p) { if(s==e) { t[n]=p; return; } int m=(s+e)/2; if(x>m) si(n*2+1,m+1,e,x,p); else si(n*2,s,m,x,p); t[n]=max(t[n*2],t[n*2+1]); return; } int sq(int n,int s,int e,ll p) { if(s==e) return s; int m=(s+e)/2; if(t[n*2]>=p) return sq(n*2,s,m,p); return sq(n*2+1,m+1,e,p); } int sq2(int n,int s,int e,ll p) { if(s==e) return s; int m=(s+e)/2; if(t[n*2+1]>p) return sq2(n*2+1,m+1,e,p); return sq2(n*2,s,m,p); } }st; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ft1.init(); ft2.init(); int n,q; cin>>n>>q; vector<ll>v(n); for(ll&t:v) cin>>t; vector<int>lv(n),rv(n); st.init(); for(int i=0;i<n;i++) { lv[i]=st.sq2(1,0,n-1,v[i]); if(v[lv[i]]<=v[i]||i==0) lv[i]=i-n-1; st.si(1,0,n-1,i,v[i]); } st.init(); for(int i=n;i-->0;) { rv[i]=st.sq(1,0,n-1,v[i]); if(v[rv[i]]<v[i]||i==n-1) rv[i]=n; st.si(1,0,n-1,i,v[i]); } for(int i=0;i<n;i++) st.si(1,0,n-1,i,v[i]); vector<vector<pl> >q1(n*2+2),q2(n*2+2); for(int i=0;i<n;i++) { int l=lv[i]; int r=rv[i]; ll t=v[i]; int j=i+n+1; l+=n+1; r+=n+1; q1[0].eb(j,t); q2[0].eb(j+1,-t); q1[r-j].eb(r,-t); q2[r-j].eb(j+1,t); q1[j-l].eb(j,-t); q2[j-l].eb(l+1,t); q1[r-l].eb(r,t); q2[r-l].eb(l+1,-t); } vector<vector<pair<pi,int> > >qv(n+1); vector<ll>ans(q,0); for(int i=0;i<q;i++) { int t,l,r; cin>>t>>l>>r; qv[t].eb(pi(l+n,r+n),i); } for(int i=0;i<=n;i++) { for(pl&t:q1[i]) ft1.fi(t.fi,t.se); for(pl&t:q2[i]) ft2.fi(t.fi,t.se); for(auto&t:qv[i]) ans[t.se]=ft1.fq(t.fi.fi,t.fi.se)+ft2.fq(t.fi.fi-i,t.fi.se-i); } for(ll&t:ans) cout<<t<<'\n'; cout.flush(); return 0; }

Compilation message (stderr)

ho_t5.cpp: In member function 'll fen::fq(int)':
ho_t5.cpp:39:32: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
         for(int i=x+1;i>0;i=i&i-1)
                               ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...