Submission #700994

#TimeUsernameProblemLanguageResultExecution timeMemory
700994myrcellaFire (JOI20_ho_t5)C++17
0 / 100
210 ms38904 KiB
//by szh #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 0x3f #define rep(i,a,b) for (int i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define ll long long #define mod 1000000007 #define ALL(x) x.begin(),x.end() void inc(int &a,int b) {a=(a+b)%mod;} void dec(int &a,int b) {a=(a-b+mod)%mod;} int lowbit(int x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} const int maxn = 4e5+10; struct rurq{ ll tree1[maxn],tree2[maxn]; void update(int l,int r,int val) { int pos = r+1; while (pos<maxn) { tree1[pos]-=val; tree2[pos]-=r*val; pos+=lowbit(pos); } pos = l; while (pos<maxn) { tree1[pos]+=val; tree2[pos]+=(l-1)*val; pos+=lowbit(pos); } } ll query(int pos) { ll ret = 0; int tmp = pos; while (pos) { ret += tree1[pos]*tmp; ret -= tree2[pos]; pos-=lowbit(pos); } return ret; } ll query(int l,int r) { return query(r)-query(l-1); } }vert,diag; int n,m; int a[maxn]; int lt[maxn],rt[maxn]; ll ans[maxn]; vector <pair<pii,int>> q[maxn]; vector <pair<pii,int>> upd[maxn]; void tri(int l,int r,int val) { if (l>r) return; diag.update(l+n,n+n,val); vert.update(r+1+n,n+n,-val); if (r-l+1<=n) upd[r-l+1].pb({{l,r},val}); } int main() { // freopen("input.txt","r",stdin); std::ios::sync_with_stdio(false);cin.tie(0); cin>>n>>m; rep(i,0,n) cin>>a[i]; rep(i,0,m) { int t,l,r; cin>>t>>l>>r; l--,r--; q[t].pb({{l,r},i}); } stack<int> s; rep(i,0,n) { while (!s.empty() and a[s.top()]<a[i]) s.pop(); if (s.empty()) lt[i] = i-n; else lt[i] = s.top(); s.push(i); } while (!s.empty()) s.pop(); for (int i =n-1;i>=0;i--) { while (!s.empty() and a[s.top()]<a[i]) s.pop(); if(s.empty()) rt[i] = n; else rt[i] = s.top(); s.push(i); } rep(i,0,n) { tri(lt[i]+1,rt[i]-1,a[i]); tri(lt[i]+1,i-1,-a[i]); tri(i+1,rt[i]-1,-a[i]); } rep(i,1,n+1) { for (auto j:upd[i]) { int l = j.fi.fi,r = j.fi.se, val = j.se; diag.update(l+n,n+n,-val); vert.update(r+1+n,n+n,val); } for (auto j:q[i]) { ans[j.se] = vert.query(j.fi.fi+n,j.fi.se+n) + diag.query(j.fi.fi-i+n,j.fi.se-i+n); } } rep(i,0,m) cout<<ans[i]<<"\n"; return 0; }
#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...