oj.uz

Submission #122809

# Submission time Handle Problem Language Result Execution time Memory
122809 2019-06-29T10:05:05 Z WhipppedCream Two Antennas (JOI19_antennas) C++17
100 / 100
 1040 ms 48744 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
 
const int maxn = 2e5+5;
 
int n, q;
 
ll H[maxn];
int A[maxn], B[maxn];
int ql[maxn], qr[maxn];
 
ll Res[maxn];
 
vector<int> buck[maxn];
vector<int> que[maxn];
 
ll tmp[maxn];
const int inf = 1234567890;
struct segtree
{
	struct node
	{
		ll a = -1, b = inf;
		ll res = -1;
	};
	node st[6*maxn];
	void clear()
	{
		for(int i = 0; i<= 4*n; i++)
		{
			st[i] = node();
			assert(st[i].a == -1);
		}
	}
	void build(ll *arr, int p = 1, int L = 1, int R = n)
	{
		if(L == R)
		{
			st[p].a = arr[L];
			return;
		}
		int M = (L+R)/2;
		build(arr, 2*p, L, M);
		build(arr, 2*p+1, M+1, R);
	}
	void modb(int p, ll x)
	{
		st[p].b = min(st[p].b, x);
		st[p].res = max(st[p].res, st[p].a-st[p].b);
	}
	void push(int p)
	{
        modb(2*p, st[p].b);
        modb(2*p+1, st[p].b);
        st[p].b = inf;
	}
	void update(int p)
	{
		assert(st[p].b == inf);
		st[p].a = max(st[2*p].a, st[2*p+1].a);
		st[p].res = max({st[p].res, st[2*p].res, st[2*p+1].res, st[p].a-st[p].b});
	}
	void rngb(int i, int j, ll dx, int p = 1, int L = 1, int R = n)
	{
		if(i> R || j< L) return;
		if(i<= L && R<= j)
		{
			modb(p, dx);
			return;
		}
		push(p);
		int M = (L+R)/2;
		rngb(i, j, dx, 2*p, L, M);
		rngb(i, j, dx, 2*p+1, M+1, R);
		update(p);
	}
	void pointa(int x, ll dx, int p = 1, int L = 1, int R = n)
	{
		if(L == R)
		{
			st[p].a += dx;
			st[p].b = inf;
			return;
		}
		push(p);
		int M = (L+R)/2;
		if(x<= M) pointa(x, dx, 2*p, L, M);
		else pointa(x, dx, 2*p+1, M+1, R);
		update(p);
	}
	ll ask(int i, int j, int p = 1, int L = 1, int R = n)
	{
		if(i> R || j< L) return -1;
		if(i<= L && R<= j) return st[p].res;
		push(p);
		int M = (L+R)/2;
		ll x = ask(i, j, 2*p, L, M);
		ll y = ask(i, j, 2*p+1, M+1, R);
		return max(x, y);
	}
};
 
segtree foo;
 
void solve()
{
	foo.clear();
	for(int i = 0; i<= n; i++) buck[i].clear();
	for(int i = 0; i<= n; i++) que[i].clear();
	for(int i = 1; i<= n; i++)
	{
		buck[max(1, i-A[i]+1)].pb(i);
		buck[max(1, i-B[i])].pb(-i);
	}
	for(int i = 1; i<= q; i++)
	{
		que[ql[i]].pb(i);
	}
	for(int i = 1; i<= n; i++) tmp[i] = H[i]-1e9;
	foo.build(tmp);
	for(int i = n; i>= 1; i--)
	{
		foo.rngb(min(i+A[i], n+1), min(i+B[i], n), H[i]);
		for(int k : que[i])
		{
			Res[k] = max(Res[k], foo.ask(ql[k], qr[k]));
		}
		for(int x : buck[i])
		{
			if(x> 0) foo.pointa(x, 1e9);
			else foo.pointa(-x, -1e9);
		}
	}
}
 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++)
	{
		scanf("%lld %d %d", &H[i], &A[i], &B[i]);
	}
	scanf("%d", &q);
	for(int i = 1; i<= q; i++)
	{
		scanf("%d %d", &ql[i], &qr[i]);
	}
	memset(Res, -1, sizeof Res);
	solve();
	reverse(H+1, H+n+1);
	reverse(A+1, A+n+1);
	reverse(B+1, B+n+1);
    for(int i = 1; i<= q; i++)
    {
    	int l = ql[i], r = qr[i];
    	ql[i] = n+1-r;
    	qr[i] = n+1-l;
    	assert(ql[i]<= qr[i]);
    }
    solve();
    for(int i = 1; i<= q; i++) printf("%lld\n", Res[i]);
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %d %d", &H[i], &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &ql[i], &qr[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11384 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 11 ms 11384 KB Output is correct
4 Correct 12 ms 11388 KB Output is correct
5 Correct 12 ms 11388 KB Output is correct
6 Correct 12 ms 11384 KB Output is correct
7 Correct 12 ms 11384 KB Output is correct
8 Correct 12 ms 11384 KB Output is correct
9 Correct 12 ms 11388 KB Output is correct
10 Correct 12 ms 11384 KB Output is correct
11 Correct 11 ms 11384 KB Output is correct
12 Correct 12 ms 11384 KB Output is correct
13 Correct 12 ms 11384 KB Output is correct
14 Correct 12 ms 11384 KB Output is correct
15 Correct 12 ms 11384 KB Output is correct
16 Correct 14 ms 11384 KB Output is correct
17 Correct 14 ms 11384 KB Output is correct
18 Correct 14 ms 11384 KB Output is correct
19 Correct 12 ms 11384 KB Output is correct
20 Correct 12 ms 11384 KB Output is correct
21 Correct 20 ms 11300 KB Output is correct
22 Correct 12 ms 11384 KB Output is correct
23 Correct 12 ms 11384 KB Output is correct
24 Correct 14 ms 11384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11384 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 11 ms 11384 KB Output is correct
4 Correct 12 ms 11388 KB Output is correct
5 Correct 12 ms 11388 KB Output is correct
6 Correct 12 ms 11384 KB Output is correct
7 Correct 12 ms 11384 KB Output is correct
8 Correct 12 ms 11384 KB Output is correct
9 Correct 12 ms 11388 KB Output is correct
10 Correct 12 ms 11384 KB Output is correct
11 Correct 11 ms 11384 KB Output is correct
12 Correct 12 ms 11384 KB Output is correct
13 Correct 12 ms 11384 KB Output is correct
14 Correct 12 ms 11384 KB Output is correct
15 Correct 12 ms 11384 KB Output is correct
16 Correct 14 ms 11384 KB Output is correct
17 Correct 14 ms 11384 KB Output is correct
18 Correct 14 ms 11384 KB Output is correct
19 Correct 12 ms 11384 KB Output is correct
20 Correct 12 ms 11384 KB Output is correct
21 Correct 20 ms 11300 KB Output is correct
22 Correct 12 ms 11384 KB Output is correct
23 Correct 12 ms 11384 KB Output is correct
24 Correct 14 ms 11384 KB Output is correct
25 Correct 142 ms 16428 KB Output is correct
26 Correct 31 ms 12152 KB Output is correct
27 Correct 188 ms 18424 KB Output is correct
28 Correct 191 ms 18552 KB Output is correct
29 Correct 127 ms 16376 KB Output is correct
30 Correct 137 ms 16248 KB Output is correct
31 Correct 147 ms 17500 KB Output is correct
32 Correct 201 ms 18488 KB Output is correct
33 Correct 175 ms 18056 KB Output is correct
34 Correct 99 ms 14936 KB Output is correct
35 Correct 192 ms 18552 KB Output is correct
36 Correct 199 ms 18524 KB Output is correct
37 Correct 112 ms 14968 KB Output is correct
38 Correct 185 ms 17528 KB Output is correct
39 Correct 39 ms 12536 KB Output is correct
40 Correct 181 ms 17528 KB Output is correct
41 Correct 138 ms 16124 KB Output is correct
42 Correct 189 ms 17528 KB Output is correct
43 Correct 69 ms 13688 KB Output is correct
44 Correct 185 ms 17528 KB Output is correct
45 Correct 43 ms 12664 KB Output is correct
46 Correct 182 ms 17528 KB Output is correct
47 Correct 57 ms 13176 KB Output is correct
48 Correct 180 ms 17528 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 37016 KB Output is correct
2 Correct 556 ms 39916 KB Output is correct
3 Correct 377 ms 31452 KB Output is correct
4 Correct 561 ms 40016 KB Output is correct
5 Correct 237 ms 24660 KB Output is correct
6 Correct 560 ms 40044 KB Output is correct
7 Correct 508 ms 36072 KB Output is correct
8 Correct 559 ms 40156 KB Output is correct
9 Correct 78 ms 15860 KB Output is correct
10 Correct 575 ms 39912 KB Output is correct
11 Correct 323 ms 29264 KB Output is correct
12 Correct 567 ms 39880 KB Output is correct
13 Correct 383 ms 38896 KB Output is correct
14 Correct 376 ms 38780 KB Output is correct
15 Correct 371 ms 37740 KB Output is correct
16 Correct 356 ms 38084 KB Output is correct
17 Correct 390 ms 39272 KB Output is correct
18 Correct 379 ms 38252 KB Output is correct
19 Correct 378 ms 38376 KB Output is correct
20 Correct 382 ms 38936 KB Output is correct
21 Correct 363 ms 39144 KB Output is correct
22 Correct 375 ms 38788 KB Output is correct
23 Correct 377 ms 38428 KB Output is correct
24 Correct 353 ms 37740 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11384 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 11 ms 11384 KB Output is correct
4 Correct 12 ms 11388 KB Output is correct
5 Correct 12 ms 11388 KB Output is correct
6 Correct 12 ms 11384 KB Output is correct
7 Correct 12 ms 11384 KB Output is correct
8 Correct 12 ms 11384 KB Output is correct
9 Correct 12 ms 11388 KB Output is correct
10 Correct 12 ms 11384 KB Output is correct
11 Correct 11 ms 11384 KB Output is correct
12 Correct 12 ms 11384 KB Output is correct
13 Correct 12 ms 11384 KB Output is correct
14 Correct 12 ms 11384 KB Output is correct
15 Correct 12 ms 11384 KB Output is correct
16 Correct 14 ms 11384 KB Output is correct
17 Correct 14 ms 11384 KB Output is correct
18 Correct 14 ms 11384 KB Output is correct
19 Correct 12 ms 11384 KB Output is correct
20 Correct 12 ms 11384 KB Output is correct
21 Correct 20 ms 11300 KB Output is correct
22 Correct 12 ms 11384 KB Output is correct
23 Correct 12 ms 11384 KB Output is correct
24 Correct 14 ms 11384 KB Output is correct
25 Correct 142 ms 16428 KB Output is correct
26 Correct 31 ms 12152 KB Output is correct
27 Correct 188 ms 18424 KB Output is correct
28 Correct 191 ms 18552 KB Output is correct
29 Correct 127 ms 16376 KB Output is correct
30 Correct 137 ms 16248 KB Output is correct
31 Correct 147 ms 17500 KB Output is correct
32 Correct 201 ms 18488 KB Output is correct
33 Correct 175 ms 18056 KB Output is correct
34 Correct 99 ms 14936 KB Output is correct
35 Correct 192 ms 18552 KB Output is correct
36 Correct 199 ms 18524 KB Output is correct
37 Correct 112 ms 14968 KB Output is correct
38 Correct 185 ms 17528 KB Output is correct
39 Correct 39 ms 12536 KB Output is correct
40 Correct 181 ms 17528 KB Output is correct
41 Correct 138 ms 16124 KB Output is correct
42 Correct 189 ms 17528 KB Output is correct
43 Correct 69 ms 13688 KB Output is correct
44 Correct 185 ms 17528 KB Output is correct
45 Correct 43 ms 12664 KB Output is correct
46 Correct 182 ms 17528 KB Output is correct
47 Correct 57 ms 13176 KB Output is correct
48 Correct 180 ms 17528 KB Output is correct
49 Correct 502 ms 37016 KB Output is correct
50 Correct 556 ms 39916 KB Output is correct
51 Correct 377 ms 31452 KB Output is correct
52 Correct 561 ms 40016 KB Output is correct
53 Correct 237 ms 24660 KB Output is correct
54 Correct 560 ms 40044 KB Output is correct
55 Correct 508 ms 36072 KB Output is correct
56 Correct 559 ms 40156 KB Output is correct
57 Correct 78 ms 15860 KB Output is correct
58 Correct 575 ms 39912 KB Output is correct
59 Correct 323 ms 29264 KB Output is correct
60 Correct 567 ms 39880 KB Output is correct
61 Correct 383 ms 38896 KB Output is correct
62 Correct 376 ms 38780 KB Output is correct
63 Correct 371 ms 37740 KB Output is correct
64 Correct 356 ms 38084 KB Output is correct
65 Correct 390 ms 39272 KB Output is correct
66 Correct 379 ms 38252 KB Output is correct
67 Correct 378 ms 38376 KB Output is correct
68 Correct 382 ms 38936 KB Output is correct
69 Correct 363 ms 39144 KB Output is correct
70 Correct 375 ms 38788 KB Output is correct
71 Correct 377 ms 38428 KB Output is correct
72 Correct 353 ms 37740 KB Output is correct
73 Correct 860 ms 44044 KB Output is correct
74 Correct 612 ms 40996 KB Output is correct
75 Correct 785 ms 39272 KB Output is correct
76 Correct 1040 ms 48732 KB Output is correct
77 Correct 518 ms 30184 KB Output is correct
78 Correct 859 ms 46640 KB Output is correct
79 Correct 890 ms 44520 KB Output is correct
80 Correct 1035 ms 48744 KB Output is correct
81 Correct 342 ms 21492 KB Output is correct
82 Correct 772 ms 45252 KB Output is correct
83 Correct 727 ms 36716 KB Output is correct
84 Correct 1014 ms 48744 KB Output is correct
85 Correct 652 ms 44152 KB Output is correct
86 Correct 829 ms 46228 KB Output is correct
87 Correct 453 ms 39532 KB Output is correct
88 Correct 809 ms 45420 KB Output is correct
89 Correct 732 ms 45588 KB Output is correct
90 Correct 827 ms 45844 KB Output is correct
91 Correct 536 ms 41968 KB Output is correct
92 Correct 823 ms 46028 KB Output is correct
93 Correct 463 ms 40960 KB Output is correct
94 Correct 844 ms 46316 KB Output is correct
95 Correct 548 ms 41496 KB Output is correct
96 Correct 773 ms 45044 KB Output is correct