oj.uz

Submission #626354

# Submission time Handle Problem Language Result Execution time Memory
626354 2022-08-11T12:02:23 Z PoPularPlusPlus Radio Towers (IOI22_towers) C++17
0 / 100
 614 ms 2768 KB 
#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

struct Seg {
	int siz = 1;
	vector<int> sums;
	void init(int n){
		while(siz < n)siz*=2;
		
		sums.assign(siz * 2, 0LL);
	}
	
	void build(vector<int>& 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<int>& 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);
	}
	
	int 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);
	}
	
	int sum(int l , int r){
		return sum(l , r , 0 , 0 , siz);
	}
	
};


vector<int> arr;

Seg st;

void init(int n, std::vector<int> h) {
	arr = h;
	st.init(n+1);
	vector<int> a(n,0);
	for(int i = 0; i < n; i++){
		int cnt = 0;
		if(i - 1 < 0 || arr[i] > arr[i-1])cnt++;
		if(i + 1 == n || arr[i + 1] < arr[i])cnt++;
		if(cnt == 2)a[i] = 1;
	}
	st.build(a);
}

int max_towers(int l , int r , int d) {
	return min(r - l + 1 , 1 + st.sum(l , r+1));
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 ms 1696 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '18'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '18'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 614 ms 2768 KB 1st lines differ - on the 1st token, expected: '11903', found: '11904'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 848 KB 1st lines differ - on the 1st token, expected: '7197', found: '8005'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '18'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 477 ms 1696 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -