제출 #501646

#제출 시각아이디문제언어결과실행 시간메모리
501646balbitFire (JOI20_ho_t5)C++14
100 / 100
874 ms115288 KiB
#include <bits/stdc++.h> #define int ll using namespace std; #define ll long long #define y1 zck_is_king #define pii pair<ll, ll> #define ull unsigned ll #define f first #define s second #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define SQ(x) (x)*(x) #define MN(a,b) a = min(a,(__typeof__(a))(b)) #define MX(a,b) a = max(a,(__typeof__(a))(b)) #define pb push_back #define REP(i,n) for (int i = 0; i<n; ++i) #define RREP(i,n) for (int i = n-1; i>=0; --i) #define REP1(i,n) for (int i = 1; i<=n; ++i) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #ifdef BALBIT #define IOS() #define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__); template<typename T> void _do(T &&x){cerr<<x<<endl;} template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);} #else #define IOS() ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' #define bug(...) #endif const int iinf = 1e9+10; const ll inf = 1ll<<60; const ll mod = 1e9+7 ; void GG(){cout<<"0\n"; exit(0);} ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod ll re=1; while (n>0){ if (n&1) re = re*a %mo; a = a*a %mo; n>>=1; } return re; } ll inv (ll b, ll mo = mod){ if (b==1) return b; return (mo-mo/b) * inv(mo%b,mo) % mo; } const int maxn = 4e5+10; struct act{ int l, v; }; struct seg{ ll s[maxn*4], tg[maxn*4]; void push(int o, int l, int r){ if (tg[o]) { s[o] += tg[o] * (r-l+1); if (l!=r) { tg[o*2] += tg[o]; tg[o*2+1] += tg[o]; } tg[o] = 0; } } void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) { push(o,l,r); if (l>R || r<L) return; if (l >= L && r <= R) { tg[o] += v; push(o,l,r); return; } int mid = (l+r)/2; MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r); s[o] = (s[o*2]+ s[o*2+1]); } ll QU(int L, int R, int o=1, int l=0, int r=maxn-1) { push(o,l,r); if (l>R || r<L) return 0; if (l>=L && r<=R) { return s[o]; } int mid = (l+r)/2; return (QU(L,R,o*2,l,mid)+ QU(L,R,o*2+1,mid+1,r)); } void go(act A) { MO(max(A.l,0ll), maxn-1, A.v); } seg(){ memset(s, 0, sizeof s); memset(tg, 0, sizeof tg); } }; seg straight, slant; vector<act> straighta[maxn], slanta[maxn]; void Tri(int a, int b, int v) { if (v == 0) return; bug("tri", a, b, v); int steps = b-a+1; straight.MO(b+1, maxn-1, -v); slant.MO(a, maxn-1, v); if (steps < maxn) { straighta[steps].pb({b+1, +v}); slanta[steps].pb({a, -v}); } } int lbig[maxn], rbig[maxn]; int a[maxn]; ll ask(int t, int l, int r) { ll str = straight.QU(l,r); ll sla = slant.QU(max(l-t,0ll), max(r-t,0ll)); return str + sla; } ll ans[maxn]; struct que{ int t, l, r, id; }; signed main(){ IOS(); bug(1,2); int n; cin>>n; int q; cin>>q; REP(i,n) { cin>>a[i]; } { vector<pii> yo; yo.pb({-n-2,inf}); // stuff on the left are bigger REP(i,n) { while (yo.back().s < a[i]) { yo.pop_back(); } lbig[i] = yo.back().f; yo.pb({i, a[i]}); bug(i, lbig[i]); } } { vector<pii> yo; yo.pb({n,inf}); // stuff on the left are bigger RREP(i,n) { while (yo.back().s <= a[i]) { // leq here yo.pop_back(); } rbig[i] = yo.back().f; yo.pb({i, a[i]}); bug(i, rbig[i]); } } REP(i,n) { int prv = lbig[i] + 1; int j = rbig[i] - 1; Tri(prv, j, a[i]); Tri(prv, i-1, -a[i]); Tri(i+1, j, -a[i]); } vector<que> bar; REP(i,q) { int t,l,r; cin>>t>>l>>r; --l; --r; bar.pb({t,l,r,i}); } sort(ALL(bar), [&](que a, que b){return a.t < b.t;}); int nat = -1; for (auto e : bar) { while (nat < e.t) { ++nat; bug(nat); for (act a : straighta[nat]) { bug("straight", a.l, a.v); straight.go(a); } for (act a : slanta[nat]) { bug(a.l, a.v); slant.go(a); } } ans[e.id] = ask(e.t, e.l, e.r); } REP(i,q) { cout<<ans[i]<<endl; } } /* 5 3 5 0 0 0 0 0 1 3 1 1 3 2 1 3 */
#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...