Submission #1087274

#TimeUsernameProblemLanguageResultExecution timeMemory
1087274dwuyFire (JOI20_ho_t5)C++14
100 / 100
509 ms142528 KiB
/** - dwuy -       />  フ       |  _  _|       /`ミ _x ノ      /      |     /  ヽ   ?  / ̄|   | | |  | ( ̄ヽ__ヽ_)_)  \二つ **/ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) (int)((s).size()) #define MASK(k)(1LL<<(k)) #define TASK "test" #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 200005; struct Node{ int cnts, cntt, sums, sumt, lazy; Node() : cnts(0), cntt(0), sums(0), sumt(0), lazy(0) {} }; struct SMT{ int n; vector<Node> tree; SMT(int n = 0){ this->n = n; this->tree.assign(n<<2|3, Node()); } void down(int id){ if(tree[id].lazy == 0) return; int val = tree[id].lazy; int ID = id<<1; tree[ID].lazy += val; tree[ID].cnts += val*tree[ID].cntt; tree[ID].sums += val*tree[ID].sumt; tree[ID|1].lazy += val; tree[ID|1].cnts += val*tree[ID|1].cntt; tree[ID|1].sums += val*tree[ID|1].sumt; tree[id].lazy = 0; } Node combine(Node a, Node b){ Node res; res.cntt = a.cntt + b.cntt; res.cnts = a.cnts + b.cnts; res.sumt = a.sumt + b.sumt; res.sums = a.sums + b.sums; return res; } void byebye(int pos){ int id = 1; for(int lo=1, hi=n; lo<hi;){ int mid = (lo + hi)>>1; down(id); if(pos <= mid) hi = mid, id = id<<1; else lo = mid + 1, id = id<<1|1; } tree[id] = Node(); for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]); } void update(int pos, int val, int cnt){ int id = 1; for(int lo=1, hi=n; lo<hi;){ int mid = (lo + hi)>>1; down(id); if(pos <= mid) hi = mid, id = id<<1; else lo = mid + 1, id = id<<1|1; } tree[id].cntt = 1; tree[id].cnts = cnt; tree[id].sumt = val; tree[id].sums = val*cnt; for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]); } void query(int f){ tree[1].lazy += f; tree[1].cnts += tree[1].cntt * f; tree[1].sums += tree[1].sumt * f; } }; int n, q; int a[MX]; int pl[MX]; int pr[MX]; int ans[MX]; int T[MX], L[MX], R[MX]; vector<int> G[MX]; vector<int> P0[MX]; vector<int> P1[MX]; vector<int> P2[MX]; void nhap(){ cin >> n >> q; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=q; i++){ cin >> T[i] >> L[i] >> R[i]; G[T[i]].push_back(i); } } void calcPL(){ stack<int> st; for(int i=1; i<=n; i++){ while(st.size() && a[st.top()] < a[i]) st.pop(); pl[i] = st.size()? st.top() : -1e9; st.push(i); } } void calcPR(){ stack<int> st; for(int i=n; i>=1; i--){ while(st.size() && a[st.top()] <= a[i]) st.pop(); pr[i] = st.size()? st.top() : n + 1; st.push(i); } } void solve(){ calcPL(); calcPR(); for(int i=1; i<=n; i++){ P0[min(pr[i] - i, i - pl[i])].push_back(i); if(pl[i] > 0){ P1[max(pr[i] - i, i - pl[i])].push_back(i); P2[pr[i] - pl[i]].push_back(i); } } SMT Add(n); SMT Keep(n); SMT Die(n); for(int i=1; i<=n; i++) Add.update(i, a[i], 1); for(int t=1; t<=n; t++){ for(int u: P0[t]){ Add.byebye(u); Keep.update(u, a[u], min(pr[u] - u, u - pl[u])); } for(int u: P1[t]){ Keep.byebye(u); Die.update(u, a[u], min(pr[u] - u, u - pl[u])); } for(int u: P2[t]){ Die.byebye(u); } Add.query(1); Die.query(-1); for(int i: G[t]){ int l = L[i]; int r = R[i]; function<int(int)> dwuy = [&](int k) -> int { int res = 0; int id, lo, hi; for(id=1, lo=1, hi=n; lo<hi;){ int mid = (lo + hi)>>1; Add.down(id); Die.down(id); int cnt = Add.tree[id<<1].cnts + Die.tree[id<<1].cnts + Keep.tree[id<<1].cnts; if(cnt < k){ k -= cnt; res += Add.tree[id<<1].sums + Keep.tree[id<<1].sums + Die.tree[id<<1].sums; id = id<<1|1; lo = mid + 1; } else hi = mid, id = id<<1; } int cnt = Add.tree[id].cnts + Die.tree[id].cnts + Keep.tree[id].cnts; if(cnt < k){ k -= cnt; res += Add.tree[id].sums + Keep.tree[id].sums + Die.tree[id].sums; lo++; } return res + a[lo] * k; }; ans[i] = dwuy(r) - dwuy(l - 1); } } for(int i=1; i<=q; i++) cout << ans[i] << '\n'; } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); return 0; } /* 20 20 2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1 1 1 14 2 3 18 4 10 15 8 2 17 9 20 20 4 8 19 7 2 20 11 1 5 13 2 8 20 1 20 2 12 15 7 1 14 12 7 18 14 2 17 9 19 20 12 12 12 6 2 15 11 2 15 19 12 17 4 1 20 */
#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...