oj.uz

Submission #372362

# Submission time Handle Problem Language Result Execution time Memory
372362 2021-02-27T21:07:20 Z crackersamdjam Fire (JOI20_ho_t5) C++17
8 / 100
 1000 ms 56940 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 = 20;

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(){
	#ifndef LOCAL
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#endif
	
	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:44:6: warning: unused variable 'last' [-Wunused-variable]
   44 |   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 1 ms 1260 KB Output is correct
9 Correct 2 ms 1260 KB Output is correct
10 Correct 2 ms 1260 KB Output is correct
11 Correct 2 ms 1260 KB Output is correct
12 Correct 1 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 1 ms 1260 KB Output is correct
17 Correct 1 ms 1280 KB Output is correct
18 Correct 1 ms 1272 KB Output is correct
19 Correct 2 ms 1280 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 1260 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 2 ms 1260 KB Output is correct
27 Correct 1 ms 1260 KB Output is correct
28 Correct 2 ms 1260 KB Output is correct
29 Correct 1 ms 1280 KB Output is correct
30 Correct 1 ms 1260 KB Output is correct
31 Correct 1 ms 1260 KB Output is correct
32 Correct 1 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 897 ms 56848 KB Output is correct
3 Execution timed out 1076 ms 56428 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 525 ms 55788 KB Output is correct
3 Correct 436 ms 54636 KB Output is correct
4 Correct 789 ms 56940 KB Output is correct
5 Correct 536 ms 55276 KB Output is correct
6 Correct 779 ms 56044 KB Output is correct
7 Correct 435 ms 56044 KB Output is correct
8 Correct 533 ms 55428 KB Output is correct
9 Correct 436 ms 54764 KB Output is correct
10 Correct 770 ms 54764 KB Output is correct
11 Correct 621 ms 56940 KB Output is correct
12 Correct 429 ms 56172 KB Output is correct
13 Correct 853 ms 56428 KB Output is correct
14 Correct 768 ms 55148 KB Output is correct
15 Correct 558 ms 56556 KB Output is correct
16 Correct 838 ms 56468 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 51308 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 1 ms 1260 KB Output is correct
9 Correct 2 ms 1260 KB Output is correct
10 Correct 2 ms 1260 KB Output is correct
11 Correct 2 ms 1260 KB Output is correct
12 Correct 1 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 1 ms 1260 KB Output is correct
17 Correct 1 ms 1280 KB Output is correct
18 Correct 1 ms 1272 KB Output is correct
19 Correct 2 ms 1280 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 1260 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 2 ms 1260 KB Output is correct
27 Correct 1 ms 1260 KB Output is correct
28 Correct 2 ms 1260 KB Output is correct
29 Correct 1 ms 1280 KB Output is correct
30 Correct 1 ms 1260 KB Output is correct
31 Correct 1 ms 1260 KB Output is correct
32 Correct 1 ms 1260 KB Output is correct
33 Correct 897 ms 56848 KB Output is correct
34 Execution timed out 1076 ms 56428 KB Time limit exceeded
35 Halted 0 ms 0 KB -