| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 236905 | rajarshi_basu | Fire (JOI20_ho_t5) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
//#define int ll
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define iiii pair<iii,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
//#define mp make_pair
#define vv vector
#define endl '\n'
using namespace std;
const int MAXN = 200*1000 + 5;
const int MAXT = 263*1000;
struct SegmentTree{
ll st[2*MAXT];
void update(int node,int ss,int se,int pos,ll val){
if(pos < ss or se < pos)return;
if(ss == se){
st[node] = val;
return;
}
int mid = (ss+se)/2;
update(node*2+1,ss,mid,pos,val);
update(node*2+2,mid+1,se,pos,val);
st[node] = st[node*2+1]+st[node*2+2];
}
ll get(int node,int ss,int se,int l,int r){
if(l > se or r < ss)return 0;
if(l <= ss and se <= r)return st[node];
int mid = (ss+se)/2;
return get(node*2+1,ss,mid,l,r)+get(node*2+2,mid+1,se,l,r);
}
};
/*
stage 1: still growing towards left. : sum of elements*time
stage 2(a): end growing and stabilise: sum of elementrange.
stage 2(b): grow and decay, hence no change: sum of element range
stage 3: just decay: sum(elementrange) - sum(element size)*time
stage 4: dead. We dont really need to keep track of this.
// lets see how we can better the implementation. We have a period when there is a growth
and then we have a period where there is a decay. Stage 2(a/b) can be calculated in terms of those.
stage 4 is bleh, just kick it out.
growth_end(i) = time when growth stops.
decay_start(i) = time when decay starts.
dead(i) = when we dont need to consider it.
for every viable i, ans is Arr[i]*(min(growth_end(i),t) - max(0,t-decay_start(i)))
=> Arr[i]*(min(growth_end(i),t)) - Arr[i]*(max(0,t-decay_start(i)));
*/
int D = 0;
int n;
struct Event{
// =1 means growth_end(i) has been reached, and it wont grow anymore;
// =2 means decay has been started.
// type2 = ded.
int type;
int time;
int item;
Event(int a,int b,int c){
type = a;
time = b;
item = c;
}
};
int prev_greater[MAXN];
int next_greater[MAXN];
int arr[MAXN];
void generateGreaters(int n){
stack<int> st1;
stack<int> st2;
FOR(i,n){
while(!st1.empty() and arr[st1.top()] < arr[i])st1.pop();
if(st1.empty())prev_greater[i] = -3*n;
else prev_greater[i] = st1.top();
st1.push(i);
while(!st2.empty() and arr[st2.top()] <= arr[n-i-1])st2.pop();
if(st2.empty())next_greater[n-i-1] = n;
else next_greater[n-i-1] = st2.top();
st2.push(n-i-1);
}
}
vv<Event> eventlist;
void formEventList(int n){
FOR(i,n){
int delta1 = next_greater[i] - i;
eventlist.pb(Event(1,delta1,i));
int delta2 = i - prev_greater[i];
delta2--;
eventlist.pb(Event(2,delta2,i));
eventlist.pb(Event(3,delta2+delta1,i));
}
sort(eventlist.begin(), eventlist.end(),[&](Event e1,Event e2){
if(e1.time == e2.time)return e1.type < e2.type;
return e1.time < e2.time;
});
}
SegmentTree segtree_expansion;// for expansion
SegmentTree segtree_stable;// when no expansion
SegmentTree segtree_decay;// when there is decay
SegmentTree segtree_decay_helper;
bool growthState[MAXN];
bool stableState[MAXN];
bool decayState[MAXN];
bool deadState[MAXN];
const int LOGN = 18;
ll sparseTable[LOGN][MAXN];
void generateSparseTable(){
FOR(i,n)sparseTable[0][i] = prev_greater[i];
FORE(i,1,LOGN-1){
FOR(j,n){
int p = sparseTable[i-1][j];
if(p < 0 )sparseTable[i][j] = p;
else sparseTable[i][j] = sparseTable[i-1][p];
}
}
}
ll getAnsForPrefix(int x,int t){
ll cost = 0;
int xcp = x;
for(int goUp = LOGN-1;goUp >= 0;goUp--){
if(sparseTable[goUp][x] >= 0 and xcp-sparseTable[goUp][x] <= t){
x = sparseTable[goUp][x];
}
}
//x = prev_greater[x];
//while(x >= 0 and xcp-prev_greater[x]<=t)x = prev_greater[x];
//if(D)cout << "PREFIX: " << xcp << " " << x << endl;
cost += segtree_expansion.get(0,0,n,0,x)*(t+1);// the expansion
//if(D)cout << "cost1 : " << cost << endl;
cost += segtree_stable.get(0,0,n,0,x);
//if(D)cout << "cost2 : " << cost << endl;
cost -= segtree_decay.get(0,0,n,0,x)*(t) - segtree_decay_helper.get(0,0,n,0,x);
//if(D)cout << "cost3 : " << cost << endl;
// now fix for the right most point;
cost -= (arr[x])*(min(max(0LL,t-(xcp-x)),(next_greater[x]-xcp-1)));
//if(D)cout << "cost4 : " << cost << endl;
//if(D)cout << endl;
return cost;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin >> n >> q;
FOR(i,n)cin >> arr[i];
iiii queries[q];
FOR(i,q){
int a,b,c;
cin >> a >> b >> c;
b--;c--;
queries[i] = {{a,{b,c}},i};
}
sort(queries,queries+q);
generateGreaters(n);
formEventList(n);
generateSparseTable();
reverse(eventlist.begin(), eventlist.end());
//
//if(D)cout << "OUTPUT DATA : " << endl;
//FOR(i,n)if(D)cout << next_greater[i] << " ";if(D)cout << endl;
//FOR(i,n)if(D)cout << prev_greater[i] << " ";if(D)cout << endl;
//if(D)cout << "EVENTS:" << endl;
for(auto e : eventlist){
// if(D)cout << e.type << " " << e.item << " " << e.time << endl;
}
//if(D)cout << "ACTUAL OUTPUT " << endl;
FOR(i,n)growthState[i] = 1;
FOR(i,n)segtree_expansion.update(0,0,n,i,arr[i]);
ll ans[q];
for(auto f : queries){
auto e = f.ff;
int t = e.ff;
int a = e.ss.ff;int b = e.ss.ss;
//if(D)cout << "QUERY: " << t << " " << a << " " << b << endl;
// at time t, in range a to b;
while(!eventlist.empty() and eventlist.back().time <= t){
// we have got more events to process yay !!
Event e = eventlist.back();eventlist.pop_back();
int i = e.item;
if(e.type == 1){
segtree_expansion.update(0,0,n,i,0);
segtree_stable.update(0,0,n,i,arr[i]*e.time);
growthState[i] = 0;
stableState[i] = 1;
}else if(e.type == 2){
segtree_decay.update(0,0,n,i,arr[i]);
segtree_decay_helper.update(0,0,n,i,arr[i]*e.time);
decayState[i] = 1;
}else{
// the first two are redundant
//segtree_expansion.update(0,0,n,e.item,0);
segtree_stable.update(0,0,n,i,0);
segtree_decay_helper.update(0,0,n,i,0);
segtree_decay.update(0,0,n,i,0);
decayState[i] = 0;growthState[i] =0; growthState[i] = 0;
deadState[i] = 1;
}
}
ll cost = getAnsForPrefix(b,t);
if(a != 0)cost -= getAnsForPrefix(a-1,t);
ans[f.ss] = cost;
//if(D)cout << cost << endl;
}
if(D)cout << endl;
FOR(i,q){
cout << ans[i] << endl;
}
return 0;
}