Submission #493568

#	Time	Username	Problem	Language	Result	Execution time	Memory
493568		Killer2501	Two Antennas (JOI19_antennas)	C++14	100 / 100	755 ms	65848 KiB

antennas

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "test"
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int  N = 2e5+2;
const ll mod = 998244353 ;
const ll base = 350;
const ll inf = 1e15;
ll m, n, t, k, a[N], ans, tong, b[N], c[N], res[N], l[N], r[N];
vector<ll> kq, add[N], del[N];
string s;
vector<pll> val, adj[N];
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll pw(ll k, ll n)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n&1)total = total * k % mod;
		k = k * k % mod;
	}
	return total;
}
struct BIT
{
	ll n;
	vector<ll> fe;
	BIT(ll _n)
	{
		n = _n;
		fe.resize(n+1, 0);
	}
	void add(ll id, ll x)
	{
		for(; id <= n; id += id & -id)fe[id] += x;
	}
	ll get(ll id)
	{
		ll total = 0;
		for(; id; id -= id & -id)total += fe[id];
		return total;
	}
};
struct IT
{
	ll n;
	vector<ll> mx, mn, st, lazy;
	IT(ll _n)
	{
		n =  _n;
		st.resize(n*4+4, -inf);
		mx.resize(n*4+4, -inf);
		mn.resize(n*4+4, inf);
	}
	void down(ll id)
	{
		if(mx[id] == -inf)return;
		mx[id*2] = max(mx[id*2], mx[id]);
		mx[id*2+1] = max(mx[id*2+1], mx[id]);
		st[id*2] = max(st[id*2], mx[id*2]-mn[id*2]);
		st[id*2+1] = max(st[id*2+1], mx[id*2+1]-mn[id*2+1]);
		mx[id] = -inf;
	}
	void update(ll id, ll l, ll r, ll u, ll v, ll x)
	{
		if(u <= l && r <= v)
		{
			mx[id] = max(mx[id], x);
			st[id] = max(st[id], mx[id]-mn[id]);
			return;
		}
		if(u > r || l > v)return;
		ll mid = (l+r)/2;
		down(id);
		update(id*2, l, mid, u, v, x);
		update(id*2+1, mid+1, r, u, v, x);
		st[id] = max(st[id*2], st[id*2+1]);
	}
	void update(ll l, ll r ,ll x)
	{
		update(1, 1, n, l, r, x);
	}
	void build(ll id, ll l, ll r, ll pos, ll x)
	{
		if(l == r)
		{
			mx[id] = -inf;
			mn[id] = x;
			return;
		}
		ll mid = (l+r)/2;
		down(id);
		if(pos <= mid)build(id*2, l ,mid, pos, x);
		else build(id*2+1, mid+1, r, pos, x);
		st[id] = max(st[id*2], st[id*2+1]);
		mn[id] = min(mn[id*2], mn[id*2+1]);
	}
	void build(ll pos, ll x)
	{
		build(1, 1, n, pos, x);
	}
	ll get(ll id, ll l, ll r, ll u, ll v)
	{
		if(u <= l && r <= v)return st[id];
		if(u > r || l > v)return -inf;
		down(id);
		ll mid = (l+r)/2;
		return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
	}
	ll get(ll l, ll r)
	{
		return get(1, 1, n, l, r);
	}
};
void cal()
{
	IT it(n);
	for(int i = n; i > 0; i --)
	{
		for(ll j: add[i])it.build(j, a[j]);
		for(ll j: del[i])it.build(j, inf);
		if(i-b[i] > 0)add[i-b[i]].pb(i);
		if(i-c[i]-1 > 0)del[i-c[i]-1].pb(i);
		if(i+b[i] <= n)it.update(i+b[i], min(n, i+c[i]), a[i]);
		for(pll j: adj[i])res[j.fi] = max(res[j.fi], it.get(1, j.se));
	}
}
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i] >> b[i] >> c[i];
    cin >> m;
    for(int i = 1; i <= m; i ++)
	{
		cin >> l[i] >> r[i];
		adj[l[i]].pb({i, r[i]});
		res[i] = -1;
	}
	cal();
	for(int i = 1; i <= n; i ++)
	{
		adj[i].clear();
		add[i].clear();
		del[i].clear();
	}
	for(int i = 1; i <= m; i ++)
	{
		l[i] = n-l[i]+1;
		r[i] = n-r[i]+1;
		swap(l[i], r[i]);
		adj[l[i]].pb({i, r[i]});
	}
	reverse(a+1, a+1+n);
	reverse(b+1, b+1+n);
	reverse(c+1, c+1+n);
	cal();
	for(int i = 1; i <= m; i ++)
		cout << res[i] << '\n';

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65