oj.uz

Submission #969895

# Submission time Handle Problem Language Result Execution time Memory
969895 2024-04-25T18:38:34 Z happy_node Fire (JOI20_ho_t5) C++17
100 / 100
 619 ms 154756 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=4e5+5;
const int o=2e5;

int N,Q;
ll S[MX], T[MX], L[MX], R[MX], ans[MX];

struct segtree {
        ll t[4 * MX], lazy[4 * MX];

        void push(int v, int l, int r) {
        	if(lazy[v]==0) return;

        	t[v]+=lazy[v]*(r-l+1);
        	if(l!=r) {
        		lazy[v*2+0]+=lazy[v];
        		lazy[v*2+1]+=lazy[v];
        	}
        	lazy[v]=0;
        }
 
        void update(int v, int l, int r, int ql, int qr, int val) {
        	push(v,l,r);
                if(qr<l || r<ql) return;
                if(ql<=l&&qr>=r) {
                        lazy[v]+=val;
                        push(v,l,r);
                        return;
                }
                int mid = (l + r) >> 1;
                update(v * 2 + 0, l, mid + 0, ql, qr, val);
                update(v * 2 + 1, mid + 1, r, ql, qr, val);
                t[v] = t[v * 2 + 0] + t[v * 2 + 1];
        }
 
        ll query(int v, int l, int r, int ql, int qr) {
        	push(v,l,r);
                if(ql > r || qr < l) return 0;
                if(ql <= l && qr >= r) return t[v];
                int mid = (l + r) >> 1;
                return query(v * 2 + 0, l, mid + 0, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr);
        }

        void upd(int l, int r, int val) {
        	l+=o,r+=o;
        	update(1,0,o+o,l,r,val);
        }

        ll que(int l, int r) {
        	l+=o,r+=o;
        	return query(1,0,o+o,l,r);
        }
} st, tt;

// st -> diagonal, tt -> normal segtree

vector<array<ll,3>> del[MX];
vector<array<ll,3>> qry[MX];

vector<array<ll,3>> dg[MX], vt[MX];

void tri(int l, int r, ll val) {
	if(l>r) return;

	int t=r-l+1;
	dg[0].push_back({l,o,val});
	vt[0].push_back({r+1,o,-val});

	dg[t].push_back({l,o,-val});
	vt[t].push_back({r+1,o,val});
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N>>Q;
	for(int i=1;i<=N;i++) cin>>S[i];

	vector<int> stk;
	for(int i=N;i>=1;i--) {
		while(!stk.empty() && S[stk.back()]<=S[i]) stk.pop_back();
		if(stk.size()) {
			R[i]=stk.back();
		} else {
			R[i]=N+1;
		}
		stk.push_back(i);
	}

	stk.clear();

	for(int i=1;i<=N;i++) {
		while(!stk.empty() && S[stk.back()]<S[i]) stk.pop_back();
		if(stk.size()) {
			L[i]=stk.back();
		} else {
			L[i]=-o;
		}
		stk.push_back(i);
	}

	for(int i=1;i<=Q;i++) {
		int t,l,r;
		cin>>t>>l>>r;
		qry[t].push_back({l,r,i});
	}

	for(int i=1;i<=N;i++) {
		tri(L[i]+1,R[i]-1,S[i]);
		tri(L[i]+1,i-1,-S[i]);
		tri(i+1,R[i]-1,-S[i]);
	}

	for(int t=0;t<=N;t++) {
		for(auto [l,r,val]:dg[t]) {
			st.upd(l,r,val);
		}
		for(auto [l,r,val]:vt[t]) {
			tt.upd(l,r,val);
		}
		for(auto [l,r,id]:qry[t]) {
			ans[id]=st.que(l-t,r-t)+tt.que(l,r);
		}
	}

	for(int i=1;i<=Q;i++) {
		cout<<ans[i]<<'\n';
	}

}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 58200 KB Output is correct
2 Correct 15 ms 60252 KB Output is correct
3 Correct 12 ms 62296 KB Output is correct
4 Correct 13 ms 62300 KB Output is correct
5 Correct 12 ms 62432 KB Output is correct
6 Correct 15 ms 62300 KB Output is correct
7 Correct 12 ms 62420 KB Output is correct
8 Correct 12 ms 60248 KB Output is correct
9 Correct 12 ms 62440 KB Output is correct
10 Correct 12 ms 60248 KB Output is correct
11 Correct 13 ms 62300 KB Output is correct
12 Correct 12 ms 60252 KB Output is correct
13 Correct 12 ms 60252 KB Output is correct
14 Correct 12 ms 62296 KB Output is correct
15 Correct 13 ms 62296 KB Output is correct
16 Correct 13 ms 62300 KB Output is correct
17 Correct 12 ms 62300 KB Output is correct
18 Correct 12 ms 62300 KB Output is correct
19 Correct 12 ms 62300 KB Output is correct
20 Correct 13 ms 60248 KB Output is correct
21 Correct 12 ms 60252 KB Output is correct
22 Correct 12 ms 62300 KB Output is correct
23 Correct 12 ms 62296 KB Output is correct
24 Correct 13 ms 60328 KB Output is correct
25 Correct 12 ms 60252 KB Output is correct
26 Correct 14 ms 62296 KB Output is correct
27 Correct 12 ms 62296 KB Output is correct
28 Correct 12 ms 62300 KB Output is correct
29 Correct 12 ms 60524 KB Output is correct
30 Correct 12 ms 62296 KB Output is correct
31 Correct 12 ms 60252 KB Output is correct
32 Correct 12 ms 62300 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 58200 KB Output is correct
2 Correct 588 ms 139376 KB Output is correct
3 Correct 568 ms 140712 KB Output is correct
4 Correct 537 ms 142664 KB Output is correct
5 Correct 582 ms 148912 KB Output is correct
6 Correct 554 ms 141576 KB Output is correct
7 Correct 566 ms 140568 KB Output is correct
8 Correct 559 ms 154536 KB Output is correct
9 Correct 542 ms 145096 KB Output is correct
10 Correct 530 ms 141232 KB Output is correct
11 Correct 543 ms 147116 KB Output is correct
12 Correct 520 ms 140632 KB Output is correct
13 Correct 543 ms 149648 KB Output is correct
14 Correct 590 ms 152264 KB Output is correct
15 Correct 568 ms 148640 KB Output is correct
16 Correct 584 ms 143340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 58200 KB Output is correct
2 Correct 583 ms 140676 KB Output is correct
3 Correct 507 ms 140612 KB Output is correct
4 Correct 557 ms 146220 KB Output is correct
5 Correct 520 ms 139212 KB Output is correct
6 Correct 521 ms 140376 KB Output is correct
7 Correct 542 ms 147988 KB Output is correct
8 Correct 527 ms 139964 KB Output is correct
9 Correct 541 ms 140108 KB Output is correct
10 Correct 504 ms 141036 KB Output is correct
11 Correct 550 ms 151700 KB Output is correct
12 Correct 547 ms 147080 KB Output is correct
13 Correct 531 ms 150660 KB Output is correct
14 Correct 570 ms 141644 KB Output is correct
15 Correct 618 ms 150532 KB Output is correct
16 Correct 542 ms 148848 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 140168 KB Output is correct
2 Correct 572 ms 140348 KB Output is correct
3 Correct 613 ms 139660 KB Output is correct
4 Correct 597 ms 134872 KB Output is correct
5 Correct 580 ms 134452 KB Output is correct
6 Correct 578 ms 137944 KB Output is correct
7 Correct 572 ms 143000 KB Output is correct
8 Correct 590 ms 139996 KB Output is correct
9 Correct 585 ms 138644 KB Output is correct
10 Correct 578 ms 138388 KB Output is correct
11 Correct 601 ms 136284 KB Output is correct
12 Correct 575 ms 142752 KB Output is correct
13 Correct 594 ms 135700 KB Output is correct
14 Correct 585 ms 137552 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 58200 KB Output is correct
2 Correct 15 ms 60252 KB Output is correct
3 Correct 12 ms 62296 KB Output is correct
4 Correct 13 ms 62300 KB Output is correct
5 Correct 12 ms 62432 KB Output is correct
6 Correct 15 ms 62300 KB Output is correct
7 Correct 12 ms 62420 KB Output is correct
8 Correct 12 ms 60248 KB Output is correct
9 Correct 12 ms 62440 KB Output is correct
10 Correct 12 ms 60248 KB Output is correct
11 Correct 13 ms 62300 KB Output is correct
12 Correct 12 ms 60252 KB Output is correct
13 Correct 12 ms 60252 KB Output is correct
14 Correct 12 ms 62296 KB Output is correct
15 Correct 13 ms 62296 KB Output is correct
16 Correct 13 ms 62300 KB Output is correct
17 Correct 12 ms 62300 KB Output is correct
18 Correct 12 ms 62300 KB Output is correct
19 Correct 12 ms 62300 KB Output is correct
20 Correct 13 ms 60248 KB Output is correct
21 Correct 12 ms 60252 KB Output is correct
22 Correct 12 ms 62300 KB Output is correct
23 Correct 12 ms 62296 KB Output is correct
24 Correct 13 ms 60328 KB Output is correct
25 Correct 12 ms 60252 KB Output is correct
26 Correct 14 ms 62296 KB Output is correct
27 Correct 12 ms 62296 KB Output is correct
28 Correct 12 ms 62300 KB Output is correct
29 Correct 12 ms 60524 KB Output is correct
30 Correct 12 ms 62296 KB Output is correct
31 Correct 12 ms 60252 KB Output is correct
32 Correct 12 ms 62300 KB Output is correct
33 Correct 588 ms 139376 KB Output is correct
34 Correct 568 ms 140712 KB Output is correct
35 Correct 537 ms 142664 KB Output is correct
36 Correct 582 ms 148912 KB Output is correct
37 Correct 554 ms 141576 KB Output is correct
38 Correct 566 ms 140568 KB Output is correct
39 Correct 559 ms 154536 KB Output is correct
40 Correct 542 ms 145096 KB Output is correct
41 Correct 530 ms 141232 KB Output is correct
42 Correct 543 ms 147116 KB Output is correct
43 Correct 520 ms 140632 KB Output is correct
44 Correct 543 ms 149648 KB Output is correct
45 Correct 590 ms 152264 KB Output is correct
46 Correct 568 ms 148640 KB Output is correct
47 Correct 584 ms 143340 KB Output is correct
48 Correct 583 ms 140676 KB Output is correct
49 Correct 507 ms 140612 KB Output is correct
50 Correct 557 ms 146220 KB Output is correct
51 Correct 520 ms 139212 KB Output is correct
52 Correct 521 ms 140376 KB Output is correct
53 Correct 542 ms 147988 KB Output is correct
54 Correct 527 ms 139964 KB Output is correct
55 Correct 541 ms 140108 KB Output is correct
56 Correct 504 ms 141036 KB Output is correct
57 Correct 550 ms 151700 KB Output is correct
58 Correct 547 ms 147080 KB Output is correct
59 Correct 531 ms 150660 KB Output is correct
60 Correct 570 ms 141644 KB Output is correct
61 Correct 618 ms 150532 KB Output is correct
62 Correct 542 ms 148848 KB Output is correct
63 Correct 585 ms 140168 KB Output is correct
64 Correct 572 ms 140348 KB Output is correct
65 Correct 613 ms 139660 KB Output is correct
66 Correct 597 ms 134872 KB Output is correct
67 Correct 580 ms 134452 KB Output is correct
68 Correct 578 ms 137944 KB Output is correct
69 Correct 572 ms 143000 KB Output is correct
70 Correct 590 ms 139996 KB Output is correct
71 Correct 585 ms 138644 KB Output is correct
72 Correct 578 ms 138388 KB Output is correct
73 Correct 601 ms 136284 KB Output is correct
74 Correct 575 ms 142752 KB Output is correct
75 Correct 594 ms 135700 KB Output is correct
76 Correct 585 ms 137552 KB Output is correct
77 Correct 602 ms 142676 KB Output is correct
78 Correct 596 ms 141088 KB Output is correct
79 Correct 589 ms 150356 KB Output is correct
80 Correct 610 ms 143584 KB Output is correct
81 Correct 588 ms 141796 KB Output is correct
82 Correct 592 ms 145212 KB Output is correct
83 Correct 587 ms 139656 KB Output is correct
84 Correct 601 ms 142244 KB Output is correct
85 Correct 590 ms 151304 KB Output is correct
86 Correct 601 ms 141452 KB Output is correct
87 Correct 579 ms 151684 KB Output is correct
88 Correct 576 ms 149340 KB Output is correct
89 Correct 547 ms 144012 KB Output is correct
90 Correct 577 ms 150992 KB Output is correct
91 Correct 546 ms 141216 KB Output is correct
92 Correct 544 ms 142220 KB Output is correct
93 Correct 547 ms 142988 KB Output is correct
94 Correct 558 ms 151068 KB Output is correct
95 Correct 557 ms 150404 KB Output is correct
96 Correct 574 ms 143324 KB Output is correct
97 Correct 567 ms 142464 KB Output is correct
98 Correct 572 ms 142736 KB Output is correct
99 Correct 595 ms 144376 KB Output is correct
100 Correct 619 ms 147092 KB Output is correct
101 Correct 574 ms 142732 KB Output is correct
102 Correct 604 ms 154756 KB Output is correct