oj.uz

답안 #122804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122804 2019-06-29T09:55:55 Z WhipppedCream Two Antennas (JOI19_antennas) C++17
22 / 100
 567 ms 40016 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[4*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(max(st[p].res, st[2*p].res), max(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(0, i-A[i]+1)].pb(i);
		buck[max(0, 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 481 ms 37064 KB Output is correct
2 Correct 522 ms 40008 KB Output is correct
3 Correct 347 ms 31308 KB Output is correct
4 Correct 525 ms 39920 KB Output is correct
5 Correct 220 ms 24560 KB Output is correct
6 Correct 528 ms 39912 KB Output is correct
7 Correct 451 ms 36064 KB Output is correct
8 Correct 523 ms 39852 KB Output is correct
9 Correct 71 ms 15860 KB Output is correct
10 Correct 532 ms 40008 KB Output is correct
11 Correct 305 ms 29164 KB Output is correct
12 Correct 567 ms 40016 KB Output is correct
13 Correct 359 ms 38900 KB Output is correct
14 Correct 356 ms 38636 KB Output is correct
15 Correct 369 ms 37864 KB Output is correct
16 Correct 331 ms 37864 KB Output is correct
17 Correct 366 ms 39332 KB Output is correct
18 Correct 357 ms 38232 KB Output is correct
19 Correct 353 ms 38380 KB Output is correct
20 Correct 358 ms 38892 KB Output is correct
21 Correct 345 ms 39204 KB Output is correct
22 Correct 355 ms 38764 KB Output is correct
23 Correct 350 ms 38568 KB Output is correct
24 Correct 330 ms 37612 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 11384 KB Output isn't correct
2 Halted 0 ms 0 KB -