oj.uz

Submission #486020

# Submission time Handle Problem Language Result Execution time Memory
486020 2021-11-10T07:57:11 Z PoPularPlusPlus Fire (JOI20_ho_t5) C++17
6 / 100
 194 ms 15728 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] = 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]=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 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);
	vector<int> v2;
	for(int i = 0; i < n-1; i++){
		if(arr[i] == 2 && arr[i + 1] == 1)v2.pb(i + 1);
	}
	vector<pair<pair<int,int>,pair<int,int>>> v;
	for(int i = 0; i < q; i++){
		int t , l , r;
		cin >> t >> l >> r;
		l--;
		r--;
		v.pb(mp(mp(t,i),mp(l,r)));
	}
	int ans[q];
	sv(v);
	int j = 0;
	for(int time = 1; time <= n; time++){
		for(int i : v2){
			arr[i] = 2;
			st.set(i,2);
		}
		vector<int> v1;
		for(int i : v2){
			if(i < n-1 && arr[i + 1] == 1)v1.pb(i + 1);
		}
		v2 = v1;
		while(j < q && v[j].vf.vf == time){
			ans[v[j].vf.vs] = st.sum(v[j].vs.vf , v[j].vs.vs + 1);
			j++;	
		}
	}
	for(int i = 0; i < q; i++){
		cout << ans[i] << '\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 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 11316 KB Output is correct
2 Correct 194 ms 15348 KB Output is correct
3 Correct 176 ms 15556 KB Output is correct
4 Correct 174 ms 15560 KB Output is correct
5 Correct 178 ms 15484 KB Output is correct
6 Correct 169 ms 15276 KB Output is correct
7 Correct 167 ms 15480 KB Output is correct
8 Correct 181 ms 15524 KB Output is correct
9 Correct 183 ms 15536 KB Output is correct
10 Correct 170 ms 15336 KB Output is correct
11 Correct 181 ms 15728 KB Output is correct
12 Correct 180 ms 15652 KB Output is correct
13 Correct 180 ms 15512 KB Output is correct
14 Correct 173 ms 15588 KB Output is correct

Subtask #5
0 / 80.0

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