답안 #372369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
372369 2021-02-27T21:39:52 Z crackersamdjam Fire (JOI20_ho_t5) C++17
14 / 100
1000 ms 56228 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 = 400, SZ = 500, 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];
		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
		int id = i/SZ;
		int rid = rs[i]/SZ;

		slope[id].emplace_back(i-i, a[i]);
		slope[rid].emplace_back(rs[i]-i, -a[i]);
		for(int j = id; j <= rid; j++){
			if(j != id)
				slope[j].emplace_back(j*SZ-i, a[i]);
			
			if(j != rid)
				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[id].emplace_back(i-ls[i], -a[i]);
		slope[rid].emplace_back(rs[i]-ls[i], a[i]);
		for(int j = id; j <= rid; j++){
			if(j != id)
				slope[j].emplace_back(j*SZ-ls[i], -a[i]);
			
			if(j != rid)
				slope[j].emplace_back(j*SZ+SZ-ls[i], a[i]);
		}
	}

	for(int k = 1; k <= __lg(n); k++){	
		for(int i = 1; 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]), greater<pair<int, ll>>());
	}
	
	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, qi] = 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[qi] += qu(max(1, i-t), i);
		}
		else{
			for(int i = l; i < li*SZ; i++)
				ans[qi] += qu(max(1, i-t), i);

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

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

	for(int i = 0; i < qs; i++)
		cout<<ans[i]<<'\n';
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1280 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 1280 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 1 ms 1280 KB Output is correct
9 Correct 1 ms 1260 KB Output is correct
10 Correct 2 ms 1260 KB Output is correct
11 Correct 1 ms 1260 KB Output is correct
12 Correct 1 ms 1260 KB Output is correct
13 Correct 1 ms 1280 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 2 ms 1260 KB Output is correct
19 Correct 2 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 1268 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 1 ms 1260 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 862 ms 49644 KB Output is correct
3 Correct 877 ms 49164 KB Output is correct
4 Correct 785 ms 55244 KB Output is correct
5 Correct 875 ms 56072 KB Output is correct
6 Correct 711 ms 55404 KB Output is correct
7 Correct 893 ms 55480 KB Output is correct
8 Correct 812 ms 56228 KB Output is correct
9 Correct 748 ms 56152 KB Output is correct
10 Correct 748 ms 54948 KB Output is correct
11 Correct 877 ms 56164 KB Output is correct
12 Correct 813 ms 54892 KB Output is correct
13 Correct 682 ms 55704 KB Output is correct
14 Correct 720 ms 56072 KB Output is correct
15 Correct 816 ms 55844 KB Output is correct
16 Correct 716 ms 55560 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 557 ms 49004 KB Output is correct
3 Correct 524 ms 47980 KB Output is correct
4 Correct 631 ms 50028 KB Output is correct
5 Correct 456 ms 48620 KB Output is correct
6 Correct 573 ms 49132 KB Output is correct
7 Correct 446 ms 49392 KB Output is correct
8 Correct 436 ms 48796 KB Output is correct
9 Correct 529 ms 48328 KB Output is correct
10 Correct 612 ms 47980 KB Output is correct
11 Correct 738 ms 50068 KB Output is correct
12 Correct 445 ms 49776 KB Output is correct
13 Correct 745 ms 49848 KB Output is correct
14 Correct 552 ms 48628 KB Output is correct
15 Correct 502 ms 49992 KB Output is correct
16 Correct 773 ms 49620 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 46696 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1280 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 1280 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Correct 1 ms 1280 KB Output is correct
9 Correct 1 ms 1260 KB Output is correct
10 Correct 2 ms 1260 KB Output is correct
11 Correct 1 ms 1260 KB Output is correct
12 Correct 1 ms 1260 KB Output is correct
13 Correct 1 ms 1280 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 2 ms 1260 KB Output is correct
19 Correct 2 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 1268 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 1 ms 1260 KB Output is correct
33 Correct 862 ms 49644 KB Output is correct
34 Correct 877 ms 49164 KB Output is correct
35 Correct 785 ms 55244 KB Output is correct
36 Correct 875 ms 56072 KB Output is correct
37 Correct 711 ms 55404 KB Output is correct
38 Correct 893 ms 55480 KB Output is correct
39 Correct 812 ms 56228 KB Output is correct
40 Correct 748 ms 56152 KB Output is correct
41 Correct 748 ms 54948 KB Output is correct
42 Correct 877 ms 56164 KB Output is correct
43 Correct 813 ms 54892 KB Output is correct
44 Correct 682 ms 55704 KB Output is correct
45 Correct 720 ms 56072 KB Output is correct
46 Correct 816 ms 55844 KB Output is correct
47 Correct 716 ms 55560 KB Output is correct
48 Correct 557 ms 49004 KB Output is correct
49 Correct 524 ms 47980 KB Output is correct
50 Correct 631 ms 50028 KB Output is correct
51 Correct 456 ms 48620 KB Output is correct
52 Correct 573 ms 49132 KB Output is correct
53 Correct 446 ms 49392 KB Output is correct
54 Correct 436 ms 48796 KB Output is correct
55 Correct 529 ms 48328 KB Output is correct
56 Correct 612 ms 47980 KB Output is correct
57 Correct 738 ms 50068 KB Output is correct
58 Correct 445 ms 49776 KB Output is correct
59 Correct 745 ms 49848 KB Output is correct
60 Correct 552 ms 48628 KB Output is correct
61 Correct 502 ms 49992 KB Output is correct
62 Correct 773 ms 49620 KB Output is correct
63 Execution timed out 1087 ms 46696 KB Time limit exceeded
64 Halted 0 ms 0 KB -