oj.uz

Submission #236910

# Submission time Handle Problem Language Result Execution time Memory
236910 2020-06-03T18:08:40 Z rajarshi_basu Fire (JOI20_ho_t5) C++14
100 / 100
 651 ms 52684 KB 
#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 FenwickTree{
	ll BITree[MAXN];
	ll getSum(int index) { 
	    ll sum = 0;
	    index = index + 1; 
	    while (index>0){ 
	        sum += BITree[index]; 
	        index -= index & (-index); 
	    } 
	    return sum; 
	} 
	void updateBIT(int index, ll val) { 
	    index = index + 1; 
	  	while (index <= MAXN){ 
	    	BITree[index] += val; 
		    index += index & (-index); 
	    } 
	} 
	void update(int a,int b,int c,int d,ll val){
		updateBIT(d,val - get(a,b,c,d,d));
	}
	ll get(int a,int b,int c,int l,int r){
		ll cost = getSum(r);
		if(l != 0)cost -= getSum(l-1);
		return cost;
	}
};


/*
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];
ll 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;
	});
}

FenwickTree fenwick_expansion;// for expansion
FenwickTree fenwick_stable;// when no expansion
FenwickTree fenwick_decay;// when there is decay
FenwickTree fenwick_decay_helper; // basically decay is like Arr[i]*(t-somevalue), and Arr[i]*somevalue is determined by this array.

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;

	// here we are essentially finding the element presiding over the last element. 
	for(int goUp = LOGN-1;goUp >= 0;goUp--){
		if(sparseTable[goUp][x] >= 0 and xcp-sparseTable[goUp][x] <= t){
			x = sparseTable[goUp][x];
		}
	}


	cost += fenwick_expansion.get(0,0,n,0,x)*(t+1);// the expansion
	cost += fenwick_stable.get(0,0,n,0,x);
	cost -= fenwick_decay.get(0,0,n,0,x)*(t) - fenwick_decay_helper.get(0,0,n,0,x);
	cost -= (arr[x])*(min(max(0,t-(xcp-x)),(next_greater[x]-xcp-1)));
	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()); // since we take elements from back

	FOR(i,n)fenwick_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;
		// 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){
				fenwick_expansion.update(0,0,n,i,0);
				fenwick_stable.update(0,0,n,i,arr[i]*e.time);
			}else if(e.type == 2){
				fenwick_decay.update(0,0,n,i,arr[i]);
				fenwick_decay_helper.update(0,0,n,i,arr[i]*e.time);
			}else{
				fenwick_stable.update(0,0,n,i,0);
				fenwick_decay_helper.update(0,0,n,i,0);
				fenwick_decay.update(0,0,n,i,0);
			}
		}

		ll cost = getAnsForPrefix(b,t);
		if(a != 0)cost -= getAnsForPrefix(a-1,t);
		ans[f.ss] = cost;
	}
	FOR(i,q){
		cout << ans[i] << endl;
	}

	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 768 KB Output is correct
17 Correct 5 ms 768 KB Output is correct
18 Correct 5 ms 768 KB Output is correct
19 Correct 5 ms 768 KB Output is correct
20 Correct 5 ms 768 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 5 ms 768 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 5 ms 768 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 5 ms 768 KB Output is correct
28 Correct 6 ms 768 KB Output is correct
29 Correct 5 ms 768 KB Output is correct
30 Correct 5 ms 768 KB Output is correct
31 Correct 5 ms 768 KB Output is correct
32 Correct 5 ms 768 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 371 ms 51528 KB Output is correct
3 Correct 370 ms 51252 KB Output is correct
4 Correct 363 ms 51572 KB Output is correct
5 Correct 367 ms 52272 KB Output is correct
6 Correct 386 ms 51700 KB Output is correct
7 Correct 391 ms 52028 KB Output is correct
8 Correct 360 ms 52552 KB Output is correct
9 Correct 367 ms 52040 KB Output is correct
10 Correct 359 ms 50888 KB Output is correct
11 Correct 367 ms 52300 KB Output is correct
12 Correct 350 ms 50760 KB Output is correct
13 Correct 367 ms 52168 KB Output is correct
14 Correct 357 ms 52168 KB Output is correct
15 Correct 370 ms 52172 KB Output is correct
16 Correct 353 ms 51620 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 404 ms 50636 KB Output is correct
3 Correct 376 ms 49864 KB Output is correct
4 Correct 406 ms 51784 KB Output is correct
5 Correct 433 ms 50248 KB Output is correct
6 Correct 427 ms 50888 KB Output is correct
7 Correct 427 ms 51012 KB Output is correct
8 Correct 415 ms 50380 KB Output is correct
9 Correct 390 ms 50120 KB Output is correct
10 Correct 392 ms 49608 KB Output is correct
11 Correct 391 ms 51592 KB Output is correct
12 Correct 381 ms 51272 KB Output is correct
13 Correct 404 ms 51272 KB Output is correct
14 Correct 393 ms 50120 KB Output is correct
15 Correct 398 ms 51528 KB Output is correct
16 Correct 403 ms 51144 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 49200 KB Output is correct
2 Correct 590 ms 49816 KB Output is correct
3 Correct 595 ms 50764 KB Output is correct
4 Correct 601 ms 49084 KB Output is correct
5 Correct 604 ms 49328 KB Output is correct
6 Correct 645 ms 49844 KB Output is correct
7 Correct 607 ms 50716 KB Output is correct
8 Correct 612 ms 50224 KB Output is correct
9 Correct 610 ms 49460 KB Output is correct
10 Correct 622 ms 50092 KB Output is correct
11 Correct 651 ms 49720 KB Output is correct
12 Correct 640 ms 49844 KB Output is correct
13 Correct 608 ms 49588 KB Output is correct
14 Correct 616 ms 49716 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 5 ms 768 KB Output is correct
17 Correct 5 ms 768 KB Output is correct
18 Correct 5 ms 768 KB Output is correct
19 Correct 5 ms 768 KB Output is correct
20 Correct 5 ms 768 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 5 ms 768 KB Output is correct
23 Correct 5 ms 768 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 5 ms 768 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 5 ms 768 KB Output is correct
28 Correct 6 ms 768 KB Output is correct
29 Correct 5 ms 768 KB Output is correct
30 Correct 5 ms 768 KB Output is correct
31 Correct 5 ms 768 KB Output is correct
32 Correct 5 ms 768 KB Output is correct
33 Correct 439 ms 51272 KB Output is correct
34 Correct 437 ms 52072 KB Output is correct
35 Correct 446 ms 52296 KB Output is correct
36 Correct 413 ms 51272 KB Output is correct
37 Correct 433 ms 51092 KB Output is correct
38 Correct 424 ms 51780 KB Output is correct
39 Correct 434 ms 51656 KB Output is correct
40 Correct 432 ms 50760 KB Output is correct
41 Correct 453 ms 52348 KB Output is correct
42 Correct 450 ms 51128 KB Output is correct
43 Correct 474 ms 52560 KB Output is correct
44 Correct 432 ms 52512 KB Output is correct
45 Correct 425 ms 50736 KB Output is correct
46 Correct 446 ms 52168 KB Output is correct
47 Correct 418 ms 51396 KB Output is correct
48 Correct 407 ms 50632 KB Output is correct
49 Correct 428 ms 51656 KB Output is correct
50 Correct 424 ms 52684 KB Output is correct
51 Correct 456 ms 52528 KB Output is correct
52 Correct 417 ms 51528 KB Output is correct
53 Correct 430 ms 51464 KB Output is correct
54 Correct 451 ms 51144 KB Output is correct
55 Correct 451 ms 51656 KB Output is correct
56 Correct 472 ms 51896 KB Output is correct
57 Correct 458 ms 51400 KB Output is correct
58 Correct 467 ms 52296 KB Output is correct
59 Correct 371 ms 51528 KB Output is correct
60 Correct 370 ms 51252 KB Output is correct
61 Correct 363 ms 51572 KB Output is correct
62 Correct 367 ms 52272 KB Output is correct
63 Correct 386 ms 51700 KB Output is correct
64 Correct 391 ms 52028 KB Output is correct
65 Correct 360 ms 52552 KB Output is correct
66 Correct 367 ms 52040 KB Output is correct
67 Correct 359 ms 50888 KB Output is correct
68 Correct 367 ms 52300 KB Output is correct
69 Correct 350 ms 50760 KB Output is correct
70 Correct 367 ms 52168 KB Output is correct
71 Correct 357 ms 52168 KB Output is correct
72 Correct 370 ms 52172 KB Output is correct
73 Correct 353 ms 51620 KB Output is correct
74 Correct 404 ms 50636 KB Output is correct
75 Correct 376 ms 49864 KB Output is correct
76 Correct 406 ms 51784 KB Output is correct
77 Correct 433 ms 50248 KB Output is correct
78 Correct 427 ms 50888 KB Output is correct
79 Correct 427 ms 51012 KB Output is correct
80 Correct 415 ms 50380 KB Output is correct
81 Correct 390 ms 50120 KB Output is correct
82 Correct 392 ms 49608 KB Output is correct
83 Correct 391 ms 51592 KB Output is correct
84 Correct 381 ms 51272 KB Output is correct
85 Correct 404 ms 51272 KB Output is correct
86 Correct 393 ms 50120 KB Output is correct
87 Correct 398 ms 51528 KB Output is correct
88 Correct 403 ms 51144 KB Output is correct
89 Correct 624 ms 49200 KB Output is correct
90 Correct 590 ms 49816 KB Output is correct
91 Correct 595 ms 50764 KB Output is correct
92 Correct 601 ms 49084 KB Output is correct
93 Correct 604 ms 49328 KB Output is correct
94 Correct 645 ms 49844 KB Output is correct
95 Correct 607 ms 50716 KB Output is correct
96 Correct 612 ms 50224 KB Output is correct
97 Correct 610 ms 49460 KB Output is correct
98 Correct 622 ms 50092 KB Output is correct
99 Correct 651 ms 49720 KB Output is correct
100 Correct 640 ms 49844 KB Output is correct
101 Correct 608 ms 49588 KB Output is correct
102 Correct 616 ms 49716 KB Output is correct