oj.uz

Submission #123328

# Submission time Handle Problem Language Result Execution time Memory
123328 2019-07-01T07:26:27 Z 김세빈(#3018) Two Antennas (JOI19_antennas) C++14
0 / 100
 3 ms 888 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

struct segtree{
	pii T[6060];
	int sz = 1 << 11;
	
	pii add(pii pa, pii pb)
	{
		return pii(min(pa.first, pb.first),
				max(pa.second, pb.second));
	}
	
	void insert(int p, pii v)
	{
		p += sz; T[p] = v;
		
		for(p>>=1; p; p>>=1){
			T[p] = add(T[p << 1], T[p << 1 | 1]);
		}
	}
	
	pii getval(int l, int r)
	{
		pii ret(1e9 + 1, -1e9 - 1);
		
		l += sz; r += sz;
		
		for(; l<=r; ){
			if(l & 1) ret = add(ret, T[l]);
			if(~r & 1) ret = add(ret, T[r]);
			l = l + 1 >> 1;
			r = r - 1 >> 1;
		}
		
		return ret;
	}
};

segtree T;
vector <int> V[2020];
int H[2020], A[2020], B[2020];
int Q[2020][2020];
int n, ans;

int main()
{
	int q, i, j, l, r, x, y;
	
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		scanf("%d%d%d", H + i, A + i, B + i);
		if(i + A[i] <= n) V[i + A[i]].push_back(i);
		if(i + B[i] + 1 <= n) V[i + B[i] + 1].push_back(-i);
	}
	
	for(j=1; j<=n; j++){
	
		for(i=1; i<=n; i++){
			T.insert(i, pii(1e9 + 1, -1e9 - 1));
		}
		
		ans = -1;
		
		for(i=j; i<=n; i++){
			for(int &t: V[i]){
				if(t > 0) T.insert(t, pii(H[t], H[t]));
				else T.insert(-t, pii(1e9 + 1, -1e9 - 1));
			}
			
			if(i - A[i] < 1) continue;
			
			l = max(1, i - B[i]); r = i - A[i];
			
			tie(x, y) = T.getval(l, r);
			ans = max(ans, H[i] - x);
			ans = max(ans, y - H[i]);
			
			Q[j][i] = ans;
		}
	}
	
	scanf("%d", &q);
	
	for(; q--; ){
		scanf("%d%d", &i, &j);
		printf("%d\n", Q[i][j]);
	}
	
	return 0;
}

Compilation message

antennas.cpp: In member function 'pii segtree::getval(int, int)':
antennas.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    l = l + 1 >> 1;
        ~~^~~
antennas.cpp:36:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
    r = r - 1 >> 1;
        ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", H + i, A + i, B + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &i, &j);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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