oj.uz

Submission #123327

# Submission time Handle Problem Language Result Execution time Memory
123327 2019-07-01T07:24:42 Z 김세빈(#3018) Two Antennas (JOI19_antennas) C++14
22 / 100
 188 ms 17668 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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 12664 KB Output is correct
2 Correct 172 ms 13560 KB Output is correct
3 Correct 120 ms 11000 KB Output is correct
4 Correct 175 ms 13456 KB Output is correct
5 Correct 86 ms 9028 KB Output is correct
6 Correct 180 ms 13564 KB Output is correct
7 Correct 156 ms 12408 KB Output is correct
8 Correct 183 ms 17668 KB Output is correct
9 Correct 29 ms 7160 KB Output is correct
10 Correct 185 ms 17656 KB Output is correct
11 Correct 110 ms 13276 KB Output is correct
12 Correct 188 ms 17528 KB Output is correct
13 Correct 109 ms 15732 KB Output is correct
14 Correct 109 ms 15640 KB Output is correct
15 Correct 108 ms 15736 KB Output is correct
16 Correct 116 ms 16204 KB Output is correct
17 Correct 110 ms 15988 KB Output is correct
18 Correct 121 ms 16196 KB Output is correct
19 Correct 107 ms 15724 KB Output is correct
20 Correct 110 ms 15732 KB Output is correct
21 Correct 104 ms 15384 KB Output is correct
22 Correct 108 ms 15732 KB Output is correct
23 Correct 108 ms 15728 KB Output is correct
24 Correct 108 ms 15864 KB Output is correct

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 -