oj.uz

Submission #123326

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

using namespace std;

typedef pair <int, int> pii;

struct segtree{
	pii T[606060];
	int sz = 1 << 18;
	
	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[202020];
int H[202020], A[202020], B[202020];
int n, ans;

int main()
{
	int q, i, 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);
	}
	
	scanf("%d", &q);
	
	if(q != 1) return 0;
	
	for(i=1; i<=n; i++){
		T.insert(i, pii(1e9 + 1, -1e9 - 1));
	}
	
	ans = -1;
	
	for(i=1; 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]);
	}
	
	printf("%d\n", ans);
	
	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:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:55: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:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 12924 KB Output is correct
2 Correct 177 ms 13632 KB Output is correct
3 Correct 122 ms 11100 KB Output is correct
4 Correct 182 ms 13688 KB Output is correct
5 Correct 90 ms 9080 KB Output is correct
6 Correct 173 ms 13560 KB Output is correct
7 Incorrect 149 ms 12548 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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