oj.uz

Submission #486018

# Submission time Handle Problem Language Result Execution time Memory
486018 2021-11-10T07:17:32 Z PoPularPlusPlus Fire (JOI20_ho_t5) C++17
6 / 100
 152 ms 14744 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

struct Seg {
	ll siz = 1;
	vector<ll> sums;
	void init(int n){
		while(siz < n)siz*=2;
		
		sums.assign(siz * 2, 0LL);
	}
	
	void build(vector<ll>& arr  , int x , int lx , int rx){
		if(rx-lx==1){
			if(lx < (int)arr.size()){
				sums[x] = arr[lx];
			}
			return;
		}
		int m = (lx + rx) / 2;
		build(arr , 2 * x + 1 , lx , m);
		build(arr, 2 * x + 2 , m , rx);
		sums[x] = max(sums[2 * x + 1] , sums[2 * x + 2]);
	}
	
	void build(vector<ll>& arr){
		build(arr , 0 , 0 , siz);
	}
	
	void set(int i , int v , int x , int lx , int rx){
		if(rx - lx ==1){
			sums[x] = v;
			return;
		}
		int m = (lx + rx) / 2;
		if(i < m){
			set(i , v , 2 * x + 1 , lx , m);
		}
		else {
			set(i , v , 2 * x + 2 , m , rx);
		}
		sums[x]=max(sums[2 * x + 1] , sums[2 * x + 2]);
	}
	
	void set(int x , int y){
		set(x  ,y , 0 , 0 , siz);
	}
	
	ll sum(int l , int r , int x , int lx , int rx){
		if(lx >= l && rx <= r){
			return sums[x];
		}
		if(lx >= r || rx <= l)return 0;
		int m = (lx + rx) / 2;
		return max(sum(l , r , 2 * x + 1 , lx , m) , sum(l , r , 2 * x + 2 , m , rx));
	}
	
	ll sum(int l , int r){
		return sum(l , r , 0 , 0 , siz);
	}
	
};


void solve(){
	int n,q;
	cin >> n >> q;
	vector<ll> arr(n);
	for(int i = 0; i < n; i++)cin >> arr[i];
	Seg st;
	st.init(n + 5);
	st.build(arr);
	int t1;
	cin >> t1;
	for(int i = 0; i < n; i++){
		arr[i] = st.sum(max(0,i-t1) , i + 1);
	}
	for(int i = 1; i < n; i++){
		arr[i] += arr[i-1];
	}
	int l1,r1;
	cin >> l1 >> r1;
	cout << arr[r1-1] - (l1-2 >= 0 ? arr[l1-2] : 0) << '\n';
	q--;
	while(q--){
		int t , l , r;
		cin >> t >> l >> r;
		l--;
		r--;
		cout << arr[r] - (l > 0 ? arr[l-1] : 0) << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 115 ms 12496 KB Output is correct
3 Correct 103 ms 14464 KB Output is correct
4 Correct 126 ms 14404 KB Output is correct
5 Correct 137 ms 14528 KB Output is correct
6 Correct 141 ms 14276 KB Output is correct
7 Correct 115 ms 14532 KB Output is correct
8 Correct 122 ms 14456 KB Output is correct
9 Correct 152 ms 14664 KB Output is correct
10 Correct 141 ms 14400 KB Output is correct
11 Correct 113 ms 14744 KB Output is correct
12 Correct 129 ms 14476 KB Output is correct
13 Correct 125 ms 14264 KB Output is correct
14 Correct 113 ms 14264 KB Output is correct
15 Correct 117 ms 14408 KB Output is correct
16 Correct 119 ms 14252 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

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