oj.uz

Submission #235533

# Submission time Handle Problem Language Result Execution time Memory
235533 2020-05-28T12:47:18 Z oolimry Fire (JOI20_ho_t5) C++14
13 / 100
 297 ms 37812 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#define all(x) x.begin(), x.end()
using namespace std;

const int N = 200005;
struct RURQ{
	long long tree1[400014];
	long long tree2[400014];
	
	inline void update(long long l, long long r, long long v){
		l += N, r += N;
		int L = l, R = r;
		for(r++;r <= 2*N;r += (r & -r)){
			tree1[r] -= v;
			tree2[r] -= R*v;
		}
		for(;l <= 2*N;l += (l & -l)){
			tree1[l] += v;
			tree2[l] += (L-1)*v;
		}
	}
	
	inline long long query(long long r){
		long long R = r;
		long long ans = 0;
		for(;r;r -= (r & -r)){
			ans += R * tree1[r];
			ans -= tree2[r];
		}
		return ans;
	}
	
	inline long long query(int l, int r){
		l += N, r += N;
		return query(r) - query(l-1);
	}
} vert, diag;

struct QU{ int l, r; long long v; }; //Query or Update

vector<QU> queries[200005];
vector<QU> updates[200005];
int arr[200005];
int ans[200005];
int L[200005];
int R[200005];

void tri(int l, int r, long long v){
	if(r < l) return;
	diag.update(l, N, v);
	vert.update(r+1, N, -v);
	
	if(r-l+1 < N) updates[r-l+1].push_back({l, r, v});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	
	for(int i = 1;i <= n;i++) cin >> arr[i];
	
	for(int i = 1;i <= Q;i++){
		int t, l, r; cin >> t >> l >> r;
		queries[t].push_back({l,r,i});
	}
	
	stack<int> S;
	for(int i = 1;i <= n;i++){
		while(!S.empty() && arr[S.top()] < arr[i]) S.pop();
		if(S.empty()) L[i] = -N+1;
		else L[i] = S.top();
		S.push(i);
	}
	
	while(!S.empty()) S.pop();
	for(int i = n;i >= 0;i--){
		while(!S.empty() && arr[S.top()] <= arr[i]) S.pop();
		if(S.empty()) R[i] = N-1;
		else R[i] = S.top();
		S.push(i);
	}
	
	
	for(int i = 1;i <= n;i++){
		tri(L[i]+1,R[i]-1,arr[i]);
		tri(L[i]+1,i-1,-arr[i]);
		tri(i+1,R[i]-1,-arr[i]);
	}
	
	for(int t = 1;t <= n;t++){
		for(QU u : updates[t]){
			diag.update(u.l, N, -u.v);
			vert.update(u.r+1, N, u.v);
		}
		
		for(QU q : queries[t]){
			ans[q.v] = diag.query(q.l - t, q.r - t) + vert.query(q.l, q.r);
		}
	}
	
	for(int i = 1;i <= Q;i++) cout << ans[i] << "\n";	
	
	return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9984 KB Output is correct
2 Incorrect 10 ms 9984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9984 KB Output is correct
2 Incorrect 215 ms 31456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9984 KB Output is correct
2 Correct 281 ms 33584 KB Output is correct
3 Correct 253 ms 33156 KB Output is correct
4 Correct 265 ms 34780 KB Output is correct
5 Correct 244 ms 33256 KB Output is correct
6 Correct 273 ms 33436 KB Output is correct
7 Correct 282 ms 33464 KB Output is correct
8 Correct 266 ms 33368 KB Output is correct
9 Correct 277 ms 33368 KB Output is correct
10 Correct 248 ms 32964 KB Output is correct
11 Correct 297 ms 35048 KB Output is correct
12 Correct 260 ms 34908 KB Output is correct
13 Correct 268 ms 33608 KB Output is correct
14 Correct 264 ms 33216 KB Output is correct
15 Correct 246 ms 33612 KB Output is correct
16 Correct 247 ms 33356 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 32980 KB Output is correct
2 Correct 236 ms 37256 KB Output is correct
3 Correct 234 ms 37812 KB Output is correct
4 Correct 255 ms 37316 KB Output is correct
5 Correct 244 ms 37172 KB Output is correct
6 Correct 231 ms 37044 KB Output is correct
7 Correct 248 ms 37528 KB Output is correct
8 Correct 242 ms 37432 KB Output is correct
9 Correct 247 ms 37184 KB Output is correct
10 Correct 231 ms 37432 KB Output is correct
11 Correct 239 ms 37440 KB Output is correct
12 Correct 242 ms 37428 KB Output is correct
13 Correct 229 ms 37312 KB Output is correct
14 Correct 260 ms 37304 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9984 KB Output is correct
2 Incorrect 10 ms 9984 KB Output isn't correct
3 Halted 0 ms 0 KB -