oj.uz

Submission #372363

# Submission time Handle Problem Language Result Execution time Memory
372363 2021-02-27T21:07:48 Z crackersamdjam Fire (JOI20_ho_t5) C++17
1 / 100
 1000 ms 51436 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

using namespace std;
using ll = long long;
const int MM = 2e5+5, NN = 500, SZ = 400, LOG = 18;

struct query{
	int t, l, r, id;
	bool operator<(const query &o) const{
		return t < o.t;
	}
} q[MM];

int n, qs;
ll a[MM], ans[MM], sp[LOG][MM];

ll qu(int l, int r){
	int k = __lg(r-l+1);
	return max(sp[k][l], sp[k][r-(1<<k)+1]);
}

stack<pair<int, ll>> st;
vector<pair<int, ll>> slope[NN];
ll curslope[NN], cursum[NN];
//at time i, slope changes by x
//changes sum by something

int ls[MM], rs[MM];
//rs how far will cover
//ls how far until covered

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	memset(ls, -0x3f, sizeof ls);
	cin>>n>>qs;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		sp[0][i] = a[i];
		ll last = 0;
		while(size(st) and st.top().second <= a[i]){
			auto [j, v] = st.top();
			st.pop();
			rs[j] = i;
		}

		if(size(st)){
			auto [j, v] = st.top();
			ls[i] = j;
		}

		st.emplace(i, a[i]);
	}

	while(size(st)){
		auto [j, v] = st.top();
		st.pop();
		rs[j] = n+1;
	}

	for(int i = 1; i <= n; i++){
		//this one overwrites
		slope[i/SZ].emplace_back(i-i, a[i]);
		slope[rs[i]/SZ].emplace_back(rs[i]-i, -a[i]);
		for(int j = i/SZ; j <= rs[i]/SZ; j++){
			if(j != i/SZ){
				//start
				slope[j].emplace_back(j*SZ-i, a[i]);
			}
			if(j != rs[i]/SZ){
				//end
				slope[j].emplace_back(j*SZ+SZ-i, -a[i]);
			}
		}

		//when another starts to cover a[i]
		//and when it ends covering a[i]
		// i-ls[i] to rs[i]-ls[i]

		slope[i/SZ].emplace_back(i-ls[i], -a[i]);
		slope[rs[i]/SZ].emplace_back(rs[i]-ls[i], a[i]);
		for(int j = i/SZ; j <= rs[i]/SZ; j++){
			if(j != i/SZ){
				//start
				slope[j].emplace_back(j*SZ-ls[i], -a[i]);
			}
			if(j != rs[i]/SZ){
				//end
				slope[j].emplace_back(j*SZ+SZ-ls[i], a[i]);
			}
		}
	}

	for(int k = 1; k < LOG; k++){	
		for(int i = 0; i+(1<<k)-1 <= n; i++){
			sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<(k-1))]);
		}
	}

	for(int i = 0; i <= n/SZ; i++){
		sort(all(slope[i]));
		reverse(all(slope[i]));
	}

	for(int i = 0; i < qs; i++){
		cin>>q[i].t>>q[i].l>>q[i].r;
		q[i].id = i;
	}
	sort(q, q+qs);
	int t = -1;
	for(int tt = 0; tt < qs; tt++){
		auto [nt, l, r, id] = q[tt];

		for(int j = t+1; j <= nt; j++){
			for(int i = 0; i <= n/SZ; i++){
				while(size(slope[i]) and slope[i].back().first <= j){
					curslope[i] += slope[i].back().second;
					slope[i].pop_back();
				}
				cursum[i] += curslope[i];
			}
		}
		t = nt;

		r++;
		int li = ((l+SZ-1)/SZ), ri = ((r)/SZ);

		if(li >= ri){
			for(int i = l; i < r; i++)
				ans[id] += qu(max(1, i-t), i);
		}
		else{
			for(int i = l; i < li*SZ; i++)
				ans[id] += qu(max(1, i-t), i);

			for(int i = ri*SZ; i < r; i++)
				ans[id] += qu(max(1, i-t), i);

			for(int i = li; i < ri; i++)
				ans[id] += cursum[i];
		}
	}

	for(int i = 0; i < qs; i++)
		cout<<ans[i]<<'\n';
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:42:6: warning: unused variable 'last' [-Wunused-variable]
   42 |   ll last = 0;
      |      ^~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 862 ms 51180 KB Output is correct
3 Execution timed out 1092 ms 50416 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 570 ms 50180 KB Output is correct
3 Correct 533 ms 49132 KB Output is correct
4 Correct 785 ms 51436 KB Output is correct
5 Correct 460 ms 49644 KB Output is correct
6 Correct 741 ms 50412 KB Output is correct
7 Correct 435 ms 50412 KB Output is correct
8 Correct 572 ms 49908 KB Output is correct
9 Correct 423 ms 49272 KB Output is correct
10 Correct 758 ms 49212 KB Output is correct
11 Correct 593 ms 51436 KB Output is correct
12 Correct 421 ms 50668 KB Output is correct
13 Correct 845 ms 50812 KB Output is correct
14 Correct 773 ms 49464 KB Output is correct
15 Correct 619 ms 50948 KB Output is correct
16 Execution timed out 1008 ms 51076 KB Time limit exceeded

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 47212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1260 KB Output is correct
3 Correct 1 ms 1260 KB Output is correct
4 Correct 1 ms 1260 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 1 ms 1260 KB Output is correct
10 Correct 1 ms 1260 KB Output is correct
11 Correct 1 ms 1260 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 1 ms 1260 KB Output is correct
14 Correct 1 ms 1260 KB Output is correct
15 Correct 1 ms 1260 KB Output is correct
16 Correct 2 ms 1260 KB Output is correct
17 Correct 1 ms 1260 KB Output is correct
18 Correct 1 ms 1260 KB Output is correct
19 Correct 1 ms 1260 KB Output is correct
20 Correct 1 ms 1260 KB Output is correct
21 Correct 1 ms 1260 KB Output is correct
22 Correct 1 ms 1280 KB Output is correct
23 Correct 1 ms 1260 KB Output is correct
24 Correct 1 ms 1260 KB Output is correct
25 Correct 1 ms 1260 KB Output is correct
26 Correct 1 ms 1260 KB Output is correct
27 Correct 1 ms 1260 KB Output is correct
28 Correct 1 ms 1260 KB Output is correct
29 Correct 1 ms 1260 KB Output is correct
30 Correct 1 ms 1260 KB Output is correct
31 Correct 1 ms 1260 KB Output is correct
32 Correct 2 ms 1260 KB Output is correct
33 Correct 862 ms 51180 KB Output is correct
34 Execution timed out 1092 ms 50416 KB Time limit exceeded
35 Halted 0 ms 0 KB -