Submission #1118358

#TimeUsernameProblemLanguageResultExecution timeMemory
1118358Mike_VuFire (JOI20_ho_t5)C++14
8 / 100
207 ms27564 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define MASK(x) (1LL<<(x)) #define BITj(x, j) (((x)>>(j))&1) #define ALL(v) (v).begin(), (v).end() template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } const int maxn = 2e5+5, lg = 19; struct SPT{ int sz, st[maxn][lg]; void init(int _n, int a[]) { sz = _n; memset(st, 0, sizeof(st)); for (int i = 1; i <= sz; i++) { st[i][0] = a[i]; } for (int j = 1; j < lg; j++) { if (MASK(j) >= sz) break; for (int i = 1; i+MASK(j)-1 <= sz; i++) { st[i][j] = max(st[i][j-1], st[i+MASK(j-1)][j-1]); } } } int query(int l, int r) { int k = __lg(r-l+1); return max(st[l][k], st[r-MASK(k)+1][k]); } }; struct query{ int l, r, t, id; ll ans; query(const int &_l, const int &_r, const int &_t, const int &_id) { l = _l; r = _r; t = _t; id = _id; } }; int n, q, a[maxn]; //vector<query> qu; namespace sub1{ const int maxn1 = 205; bool check(){ return max(n, q) <= maxn1; } int b[maxn1]; void solve() { while (q--) { int t, l, r; cin >> t >> l >> r; for (int i = n; i; i--) { b[i] = a[i]; for (int j = i+1; j <= min(r, i+t); j++) { maximize(b[j], a[i]); } } ll ans = 0; for (int i = l; i <= r; i++) { ans += b[i]; } cout << ans << "\n"; } } } namespace sub5{ SPT spt; ll ps1[maxn], ps2[maxn]; ///r-(l-1), l-(r+1) void solvequery(int t, int l, int r) { ll ans = 0; //bs range1 int k1, k2; int mamid = 0; //mid range if (r-t < l-1) { if (l-1 > 0) mamid = spt.query(max(r-t+1, 1), l-1); } //left k1 = max(0, l-t-1); for (int i = (r-l+2)>>1; i; i >>= 1) { while (k1+i <= r-t && spt.query(k1+i, r-t) >= max(mamid, spt.query(max(l, k1+i+1), k1+i+t))) k1 += i; } int leftbound = l-t-1; //find furthest points -> <- if (k1 > max(0, leftbound)) { int pos = max(0, l-t-1), ma = spt.query(pos+1, r-t); for (int i = (r-l+2)>>1; i; i >>= 1) { while (pos+i < k1 && spt.query(pos+i, r-t) < ma) pos += i; } ++pos; if (pos < k1) ans += ps1[k1]-ps1[pos]; ans += (ll)a[pos]*(min(pos, k1)-leftbound); leftbound = k1; // cout << pos << ' ' << k1 << ' ' << ans << "\n"; } if (k1 > max(0, l-t-1)) k2 = k1; else k2 = l-t-1; for (int i = (r-l+2)>>1; i; i >>= 1) { while (k2+i <= r-t && mamid >= spt.query(l, k2+i+t)) k2 += i; } ans += (ll)mamid*(k2-leftbound); leftbound = k2; // cout << k2 << ' ' << ans << "\n"; if (k2 < r-t) { int pos = r-t+1, ma = spt.query(max(l, r-t), r); for (int i = (r-l+2)>>1; i; i>>=1) { while (pos-i > l-t && spt.query(pos-i+t, r) < ma) pos -= i; } --pos; k2 += t; pos += t; if (pos > k2) ans += ps2[k2+1]-ps2[pos]; ans += (ll)a[pos]*(r-max(k2, pos-1)); // cout << pos << "\n"; } cout << ans; } void solve() { //prep spt.init(n, a); //prefix vector<int> id; a[0] = a[n+1] = INT_MAX; id.pb(0); ps1[0] = 0; for (int i = 1; i <= n; i++) { while (a[i] >= a[id.back()]) id.pop_back(); int las = id.back(); ps1[i] = (ll)a[i]*(i-las) + ps1[las]; id.pb(i); } id.clear(); id.pb(n+1); ps2[n+1] = 0; for (int i = n; i; i--) { while (a[i] >= a[id.back()]) id.pop_back(); int las = id.back(); ps2[i] = (ll)a[i]*(las-i) + ps2[las]; id.pb(i); } // for (int i = 1; i <= n; i++) { // cout << ps1[i] << ' '; // } // cout << "\n"; // for (int i = 1; i <= n; i++) { // cout << ps2[i] << ' '; // } // cout << "\n"; //solve query while (q--) { int l, r, t; cin >> t >> l >> r; solvequery(t, l, r); cout << "\n"; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")) { // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } cin >> n >> q; for (int i = 1; i <= n ;i++) { cin >> a[i]; } //stress if (sub1::check()) return sub1::solve(), 0; return sub5::solve(), 0; } /* 5 1 9 3 2 6 5 3 2 5 5 5 9 3 2 6 5 1 1 3 2 1 5 3 2 5 4 3 3 5 3 5 */
#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...