oj.uz

Submission #122808

# Submission time Handle Problem Language Result Execution time Memory
122808 2019-06-29T10:03:52 Z WhipppedCream Two Antennas (JOI19_antennas) C++17
22 / 100
 678 ms 39976 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), 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
0 / 2.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 11256 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 589 ms 37036 KB Output is correct
2 Correct 665 ms 39952 KB Output is correct
3 Correct 451 ms 31468 KB Output is correct
4 Correct 627 ms 39916 KB Output is correct
5 Correct 269 ms 24468 KB Output is correct
6 Correct 678 ms 39788 KB Output is correct
7 Correct 540 ms 36204 KB Output is correct
8 Correct 642 ms 39912 KB Output is correct
9 Correct 86 ms 15860 KB Output is correct
10 Correct 619 ms 39976 KB Output is correct
11 Correct 369 ms 29160 KB Output is correct
12 Correct 623 ms 39912 KB Output is correct
13 Correct 429 ms 38892 KB Output is correct
14 Correct 428 ms 38632 KB Output is correct
15 Correct 429 ms 37864 KB Output is correct
16 Correct 408 ms 37992 KB Output is correct
17 Correct 438 ms 39448 KB Output is correct
18 Correct 425 ms 38248 KB Output is correct
19 Correct 438 ms 38380 KB Output is correct
20 Correct 431 ms 38892 KB Output is correct
21 Correct 422 ms 39148 KB Output is correct
22 Correct 424 ms 38764 KB Output is correct
23 Correct 427 ms 38576 KB Output is correct
24 Correct 426 ms 37604 KB Output is correct

Subtask #4
0 / 65.0

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