Submission #866581

#	Time	Username	Problem	Language	Result	Execution time	Memory
866581		vjudge1	Radio Towers (IOI22_towers)	C++17	0 / 100	10 ms	2876 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define ls (idx<<1)
#define rs (idx<<1|1)
const int MAXN = 1e5 + 3;
const int off = (1<<20);
struct sgt {
	vector<int> t[off<1];
	int unit = 0;
	void pull(int idx){
		merge(all(t[ls]),all(t[rs]), t[idx].begin());
	}
	void build(vector<int> a, int n){
		for(int i = 0; i < n; i++){
			t[i+off] = {a[i]};
		}
		for (int i = off-1 ; i >= 1; i++){
			pull(i);
		}
	}
	int get(int l, int r, int val, int idx=1, int lo=0, int hi=off){
		if (lo<=r||l<=hi) 
			return unit;
		if (lo<=l&&r<=hi)
			return lower_bound(all(t[idx]), val) - t[idx].begin();
		int mi = (lo+hi)>>1;
		return get(l, r, ls, lo, mi)+get(l, r, rs, mi, hi);
	}
} seg;
struct sgt2 {
	int t[off<1];
	int unit;
	void pull(int idx){
		t[idx] = max(t[ls], t[rs]);
	}
	void build(vector<int> a, int n){
		memset(t, -0x3f, sizeof(t));
		unit = t[0];
		for(int i = 0; i < n; i++){
			t[i+off] = a[i];
		}
		for (int i = off-1 ; i >= 1; i++){
			pull(i);
		}
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (lo<=r||l<=hi) 
			return unit;
		if (lo<=l&&r<=hi)
			return t[idx];
		int mi = (lo+hi)>>1;
		return max(get(l, r, ls, lo, mi),get(l, r, rs, mi, hi));
	}
} seg2;
void init(int N, vector<int> H) {
	seg.build(H, N);
	seg2.build(H, N);
	return;
}
int max_towers(int L, int R, int D) {
	int mx = seg2.get(L, R+1);
	return seg.get(L, R+1, mx - D);
}

Compilation message (stderr)

towers.cpp: In member function 'void sgt2::build(std::vector<int>, int)':
towers.cpp:39:29: warning: 'memset' used with length equal to number of elements without multiplication by element size [-Wmemset-elt-size]
   39 |   memset(t, -0x3f, sizeof(t));
      |                             ^
towers.cpp:44:3: warning: iteration 2146435072 invokes undefined behavior [-Waggressive-loop-optimizations]
   44 |   for (int i = off-1 ; i >= 1; i++){
      |   ^~~
towers.cpp:44:26: note: within this loop
   44 |   for (int i = off-1 ; i >= 1; i++){
      |                        ~~^~~~
towers.cpp: In member function 'void sgt::build(std::vector<int>, int)':
towers.cpp:19:3: warning: iteration 2146435072 invokes undefined behavior [-Waggressive-loop-optimizations]
   19 |   for (int i = off-1 ; i >= 1; i++){
      |   ^~~
towers.cpp:19:26: note: within this loop
   19 |   for (int i = off-1 ; i >= 1; i++){
      |                        ~~^~~~
towers.cpp:17:20: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |                    ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:17:11: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   17 |    t[i+off] = {a[i]};
      |    ~~~~~~~^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:13:46: warning: array subscript i is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   13 |   merge(all(t[ls]),all(t[rs]), t[idx].begin());
      |                                              ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:13:46: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   13 |   merge(all(t[ls]),all(t[rs]), t[idx].begin());
      |                                              ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:13:46: warning: array subscript <unknown> is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   13 |   merge(all(t[ls]),all(t[rs]), t[idx].begin());
      |                                              ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp: In member function 'int sgt::get(int, int, int, int, int, int)':
towers.cpp:27:56: warning: array subscript mi is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:27:56: warning: array subscript mi is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:27:56: warning: array subscript lo is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:27:56: warning: array subscript hi is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:27:56: warning: array subscript mi is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:27:56: warning: array subscript mi is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp:27:56: warning: array subscript idx is outside array bounds of 'std::vector<int> [0]' [-Warray-bounds]
   27 |    return lower_bound(all(t[idx]), val) - t[idx].begin();
      |                                                        ^
towers.cpp:10:14: note: while referencing 'sgt::t'
   10 |  vector<int> t[off<1];
      |              ^
towers.cpp: In member function 'int sgt2::get(int, int, int, int, int)':
towers.cpp:52:16: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:52:16: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:52:16: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:52:16: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:52:16: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:52:16: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:52:16: warning: array subscript idx is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:52:16: warning: array subscript 1 is outside array bounds of 'int [0]' [-Warray-bounds]
   52 |    return t[idx];
      |           ~~~~~^
towers.cpp:33:6: note: while referencing 'sgt2::t'
   33 |  int t[off<1];
      |      ^
towers.cpp:56:3: note: defined here 'seg2'
   56 | } seg2;
      |   ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23