Submission #521708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521708	2022-02-02T19:09:58 Z	blue	Two Antennas (JOI19_antennas)	C++17	Compilation error	0 ms	0 KB

antennas

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long;

using vi = vector<int>;

const int mx = 200'000;
const int INF = 1'000'000'005;

int N, Q;
vi H(1+mx), A(1+mx), B(1+mx);
vi L(1+mx), R(1+mx);

const int Z = (1<<18);

struct segtree
{
	vi minH, maxLP, rawAns, l, r;

	void build(int i, int lv, int rv)
	{
		l[i] = lv, r[i] = rv;
		if(lv == rv)
		{
			minH[i] = +INF;
		}
		else
		{
			build(2*i, lv, (lv+rv)/2);
			build(2*i+1, (lv+rv)/2+1, rv);
			minH[i] = min(minH[2*i], minH[2*i+1]);
		}
	}

	void init()
	{
		minH = vi(Z<<1, INF);
		maxLP = vi(Z<<1, -INF);
		rawAns = vi(Z<<1, -INF);
		l = vi(Z<<1);
		r = vi(Z<<1);

		build(1, 1, N);
	}

	void deploy(int L, int R, int V, int i = 1)
	{
		if(r[i] < L || R < l[i]) return;
		else if(L <= l[i] && r[i] <= R)
		{
			maxLP[i] = max(maxLP[i], V);
			rawAns[i] = max(rawAns[i], maxLP[i] - minH[i]);
		}
		else
		{
			deploy(L, R, V, 2*i);
			deploy(L, R, V, 2*i+1);

			rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]});
		}
	}

	void setH(int I, int V, int i = 1)
	{
		if(l[i] == r[i]) minH[i] = V;
		else 
		{
			if(I <= (l[i]+r[i])/2) setH(I, V, 2*i);
			else setH(I, V, 2*i+1);

			minH[i] = min(minH[2*i], minH[2*i+1]);
			rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]});
		}
	}

	int query(int L, int R, int i = 1, int topMaxLP = -INF)
	{
		if(r[i] < L || R < l[i]) return -INF;
		else if(L <= l[i] && r[i] <= R)
		{
			return max(topMaxLP - minH[i], rawAns[i]);
		}
		else
		{
			topMaxLP = max(topMaxLP, maxLP[i]);
			return max(query(L, R, 2*i, topMaxLP), query(L, R, 2*i+1, topMaxLP));
		}
	}
};


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for(int i = 1; i <= N; i++)
	{
		cin >> H[i] >> A[i] >> B[i];
	}

	cin >> Q;

	for(int j = 1; j <= Q; j++)
	{
		cin >> L[j] >> R[j];
	}


	vi res(1+Q, -1);

	segtree S;

	for(int t = 0; t < 2; t++)
	{
		// cerr << "\n\n\n t = " << t << '\n';
		if(t == 1)
		{
			for(int i = 1; 2*i <= N; i++)
			{
				swap(H[i], H[N-i+1]);
				swap(A[i], A[N-i+1]);
				swap(B[i], B[N-i+1]);
			}

			for(int j = 1; j <= Q; j++)
			{
				L[j] = N+1 - L[j];
				R[j] = N+1 - R[j];
				swap(L[j], R[j]);

				// cerr << L[j] << " <> "  << R[j] << "\n";
			}
		}

		// cerr << "\n\n\n t = " << t << '\n';
		// for(int i = 1; i <= N; i++) cerr << i << " : " << H[i] << ' ' << A[i] << ' ' << B[i] << '\n';


		vi R_occ[1+N];
		for(int j = 1; j <= Q; j++)
		R_occ[R[j]].push_back(j);

		vi to_enable[1+N], to_disable[1+N];

		for(int i = 1; i <= N; i++)
		{
			if(i + A[i] <= N) to_enable[i+A[i]].push_back(i);
			if(i + B[i] + 1 <= N) to_disable[i+B[i]+1].push_back(i);
		}

		S.init();

		for(int r = 1; r <= N; r++)
		{
			// cerr << "\n\n r = " << r << '\n';
			for(int i: to_enable[r]) 
				{
					// cerr << "enable : " << i << '\n';
					S.setH(i, H[i]);
				}
			for(int i: to_disable[r]) 
				{
					// cerr << "disable : " << i << '\n';
					S.setH(i, INF);
				}

			int le = r - B[r];
			int re = r - A[r];

			if(1 <= re) 
			{
				// cerr << "deploy : " << le << ' ' << re << ' ' << H[r] << '\n';
				S.deploy(le, re, H[r]);
			}


			// for(int i = 1; i <= N; i++) cerr << S.query(i, i) << ' ';
			// 	cerr << '\n';

			for(int j: R_occ[r])
				res[j] = max(res[j], S.query(L[j], R[j]));
		}
	}

	for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
}

Compilation message

antennas.cpp:6:18: error: template argument 1 is invalid
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:8:19: note: in expansion of macro 'int'
    8 | using vi = vector<int>;
      |                   ^~~
antennas.cpp:6:18: error: template argument 2 is invalid
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:8:19: note: in expansion of macro 'int'
    8 | using vi = vector<int>;
      |                   ^~~
antennas.cpp:8:22: error: expected unqualified-id before '>' token
    8 | using vi = vector<int>;
      |                      ^
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:10:7: note: in expansion of macro 'int'
   10 | const int mx = 200'000;
      |       ^~~
antennas.cpp:10:11: error: 'mx' does not name a type
   10 | const int mx = 200'000;
      |           ^~
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:11:7: note: in expansion of macro 'int'
   11 | const int INF = 1'000'000'005;
      |       ^~~
antennas.cpp:11:11: error: 'INF' does not name a type
   11 | const int INF = 1'000'000'005;
      |           ^~~
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:13:1: note: in expansion of macro 'int'
   13 | int N, Q;
      | ^~~
antennas.cpp:13:5: error: 'N' does not name a type
   13 | int N, Q;
      |     ^
antennas.cpp:14:1: error: 'vi' does not name a type
   14 | vi H(1+mx), A(1+mx), B(1+mx);
      | ^~
antennas.cpp:15:1: error: 'vi' does not name a type
   15 | vi L(1+mx), R(1+mx);
      | ^~
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:17:7: note: in expansion of macro 'int'
   17 | const int Z = (1<<18);
      |       ^~~
antennas.cpp:17:11: error: 'Z' does not name a type
   17 | const int Z = (1<<18);
      |           ^
antennas.cpp:21:2: error: 'vi' does not name a type
   21 |  vi minH, maxLP, rawAns, l, r;
      |  ^~
antennas.cpp:6:22: error: expected ')' before ';' token
    6 | #define int long long;
      |                      ^
antennas.cpp:23:13: note: in expansion of macro 'int'
   23 |  void build(int i, int lv, int rv)
      |             ^~~
antennas.cpp:23:12: note: to match this '('
   23 |  void build(int i, int lv, int rv)
      |            ^
antennas.cpp:23:17: error: 'i' does not name a type
   23 |  void build(int i, int lv, int rv)
      |                 ^
antennas.cpp:23:24: error: 'lv' does not name a type; did you mean 'ldiv'?
   23 |  void build(int i, int lv, int rv)
      |                        ^~
      |                        ldiv
antennas.cpp:23:32: error: 'rv' does not name a type
   23 |  void build(int i, int lv, int rv)
      |                                ^~
antennas.cpp:6:22: error: expected ')' before ';' token
    6 | #define int long long;
      |                      ^
antennas.cpp:49:14: note: in expansion of macro 'int'
   49 |  void deploy(int L, int R, int V, int i = 1)
      |              ^~~
antennas.cpp:49:13: note: to match this '('
   49 |  void deploy(int L, int R, int V, int i = 1)
      |             ^
antennas.cpp:49:18: error: 'L' does not name a type
   49 |  void deploy(int L, int R, int V, int i = 1)
      |                  ^
antennas.cpp:49:25: error: 'R' does not name a type
   49 |  void deploy(int L, int R, int V, int i = 1)
      |                         ^
antennas.cpp:49:32: error: 'V' does not name a type
   49 |  void deploy(int L, int R, int V, int i = 1)
      |                                ^
antennas.cpp:49:39: error: 'i' does not name a type
   49 |  void deploy(int L, int R, int V, int i = 1)
      |                                       ^
antennas.cpp:6:22: error: expected ')' before ';' token
    6 | #define int long long;
      |                      ^
antennas.cpp:66:12: note: in expansion of macro 'int'
   66 |  void setH(int I, int V, int i = 1)
      |            ^~~
antennas.cpp:66:11: note: to match this '('
   66 |  void setH(int I, int V, int i = 1)
      |           ^
antennas.cpp:66:16: error: 'I' does not name a type
   66 |  void setH(int I, int V, int i = 1)
      |                ^
antennas.cpp:66:23: error: 'V' does not name a type
   66 |  void setH(int I, int V, int i = 1)
      |                       ^
antennas.cpp:66:30: error: 'i' does not name a type
   66 |  void setH(int I, int V, int i = 1)
      |                              ^
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:79:2: note: in expansion of macro 'int'
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |  ^~~
antennas.cpp:6:22: error: expected ')' before ';' token
    6 | #define int long long;
      |                      ^
antennas.cpp:79:12: note: in expansion of macro 'int'
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |            ^~~
antennas.cpp:79:11: note: to match this '('
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |           ^
antennas.cpp:79:6: error: ISO C++ forbids declaration of 'query' with no type [-fpermissive]
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |      ^~~~~
antennas.cpp:79:16: error: 'L' does not name a type
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |                ^
antennas.cpp:79:23: error: 'R' does not name a type
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |                       ^
antennas.cpp:79:30: error: 'i' does not name a type
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |                              ^
antennas.cpp:79:41: error: 'topMaxLP' does not name a type
   79 |  int query(int L, int R, int i = 1, int topMaxLP = -INF)
      |                                         ^~~~~~~~
antennas.cpp: In member function 'void segtree::init()':
antennas.cpp:40:3: error: 'minH' was not declared in this scope
   40 |   minH = vi(Z<<1, INF);
      |   ^~~~
antennas.cpp:40:13: error: 'Z' was not declared in this scope
   40 |   minH = vi(Z<<1, INF);
      |             ^
antennas.cpp:40:19: error: 'INF' was not declared in this scope
   40 |   minH = vi(Z<<1, INF);
      |                   ^~~
antennas.cpp:40:10: error: 'vi' was not declared in this scope
   40 |   minH = vi(Z<<1, INF);
      |          ^~
antennas.cpp:41:3: error: 'maxLP' was not declared in this scope
   41 |   maxLP = vi(Z<<1, -INF);
      |   ^~~~~
antennas.cpp:42:3: error: 'rawAns' was not declared in this scope
   42 |   rawAns = vi(Z<<1, -INF);
      |   ^~~~~~
antennas.cpp:43:3: error: 'l' was not declared in this scope
   43 |   l = vi(Z<<1);
      |   ^
antennas.cpp:44:3: error: 'r' was not declared in this scope
   44 |   r = vi(Z<<1);
      |   ^
antennas.cpp:46:15: error: 'N' was not declared in this scope
   46 |   build(1, 1, N);
      |               ^
antennas.cpp: In function 'int main()':
antennas.cpp:100:9: error: 'N' was not declared in this scope
  100 |  cin >> N;
      |         ^
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:102:6: note: in expansion of macro 'int'
  102 |  for(int i = 1; i <= N; i++)
      |      ^~~
antennas.cpp:102:10: error: 'i' was not declared in this scope
  102 |  for(int i = 1; i <= N; i++)
      |          ^
antennas.cpp:102:23: error: expected ')' before ';' token
  102 |  for(int i = 1; i <= N; i++)
      |     ~                 ^
      |                       )
antennas.cpp:102:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  102 |  for(int i = 1; i <= N; i++)
      |  ^~~
antennas.cpp:102:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  102 |  for(int i = 1; i <= N; i++)
      |                         ^
antennas.cpp:102:25: error: 'i' was not declared in this scope
antennas.cpp:107:9: error: 'Q' was not declared in this scope
  107 |  cin >> Q;
      |         ^
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:109:6: note: in expansion of macro 'int'
  109 |  for(int j = 1; j <= Q; j++)
      |      ^~~
antennas.cpp:109:10: error: 'j' was not declared in this scope
  109 |  for(int j = 1; j <= Q; j++)
      |          ^
antennas.cpp:109:23: error: expected ')' before ';' token
  109 |  for(int j = 1; j <= Q; j++)
      |     ~                 ^
      |                       )
antennas.cpp:109:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |  for(int j = 1; j <= Q; j++)
      |  ^~~
antennas.cpp:109:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |  for(int j = 1; j <= Q; j++)
      |                         ^
antennas.cpp:109:25: error: 'j' was not declared in this scope
antennas.cpp:115:2: error: 'vi' was not declared in this scope
  115 |  vi res(1+Q, -1);
      |  ^~
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:119:6: note: in expansion of macro 'int'
  119 |  for(int t = 0; t < 2; t++)
      |      ^~~
antennas.cpp:119:10: error: 't' was not declared in this scope
  119 |  for(int t = 0; t < 2; t++)
      |          ^
antennas.cpp:119:22: error: expected ')' before ';' token
  119 |  for(int t = 0; t < 2; t++)
      |     ~                ^
      |                      )
antennas.cpp:119:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  119 |  for(int t = 0; t < 2; t++)
      |  ^~~
antennas.cpp:119:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  119 |  for(int t = 0; t < 2; t++)
      |                        ^
antennas.cpp:119:24: error: 't' was not declared in this scope
antennas.cpp:6:18: error: declaration does not declare anything [-fpermissive]
    6 | #define int long long;
      |                  ^~~~
antennas.cpp:191:6: note: in expansion of macro 'int'
  191 |  for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
      |      ^~~
antennas.cpp:191:23: error: expected ')' before ';' token
  191 |  for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
      |     ~                 ^
      |                       )
antennas.cpp:191:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  191 |  for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
      |  ^~~
antennas.cpp:191:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  191 |  for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
      |                         ^
antennas.cpp:117:10: warning: unused variable 'S' [-Wunused-variable]
  117 |  segtree S;
      |          ^