oj.uz

Submission #235532

# Submission time Handle Problem Language Result Execution time Memory
235532 2020-05-28T12:42:23 Z oolimry Fire (JOI20_ho_t5) C++14
7 / 100
 270 ms 40520 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 12 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 12 ms 9984 KB Output is correct
2 Incorrect 200 ms 37128 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 12 ms 9984 KB Output is correct
2 Correct 245 ms 39136 KB Output is correct
3 Correct 264 ms 38744 KB Output is correct
4 Correct 270 ms 40404 KB Output is correct
5 Correct 258 ms 39008 KB Output is correct
6 Correct 247 ms 39000 KB Output is correct
7 Correct 254 ms 38992 KB Output is correct
8 Correct 266 ms 39128 KB Output is correct
9 Correct 263 ms 38748 KB Output is correct
10 Correct 259 ms 38388 KB Output is correct
11 Correct 269 ms 40520 KB Output is correct
12 Correct 260 ms 40240 KB Output is correct
13 Correct 258 ms 39248 KB Output is correct
14 Correct 263 ms 38880 KB Output is correct
15 Correct 269 ms 39248 KB Output is correct
16 Correct 254 ms 38864 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 36260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

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