Submission #485986

#	Time	Username	Problem	Language	Result	Execution time	Memory
485986		Killer2501	Feast (NOI19_feast)	C++14	100 / 100	196 ms	165236 KiB

feast

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "hopscotch"
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int  N = 3e5+5;
const ll mod = 1e9+7;
const ll base = 350;
const ll inf = 1e15;
ll m, n, t, k, a[N], ans, tong, b[N], d[N], h[N];
vector<pii> kq;
bool ok[N];
string s;
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 node
{
	ll mx, sum, l, r, pre, suf, nl, nr;
	node(ll _mx = -inf, ll _sum = -inf, ll _l = 0, ll _r = 0, ll _pre = -inf, ll _suf = -inf, ll _nl = 0, ll _nr = 0)
	{
		mx = _mx;
		sum = _sum;
		l = _l;
		r = _r;
		pre = _pre;
		suf = _suf;
		nl = _nl;
		nr = _nr;
	}

};
node merga(node x, node y)
{
	node res;
	res.sum = x.sum + y.sum;
	if(x.mx > y.mx)
	{
		res.mx = x.mx;
		res.l = x.l;
		res.r = x.r;
	}
	else
	{
		res.mx = y.mx;
		res.l = y.l;
		res.r = y.r;
	}
	if(res.mx < x.suf+y.pre)
	{
		res.mx = x.suf+y.pre;
		res.l = x.nr;
		res.r = y.nl;
	}
	res.pre = x.pre;
	res.nl = x.nl;
	if(res.pre < x.sum + y.pre)
	{
		res.pre = x.sum + y.pre;
		res.nl = y.nl;
	}
	res.suf = y.suf;
	res.nr = y.nr;
	if(res.suf < x.suf + y.sum)
	{
		res.suf = x.suf + y.sum;
		res.nr = x.nr;
	}
	return res;
}
struct IT
{
	ll n;
	vector<node> st, rv;
	vector<ll> lazy;
	IT(ll _n)
	{
		n = _n;
		st.resize(n*4+4);
		rv.resize(n*4+4);
		lazy.resize(n*4+4, 0);
	}
	void build(ll id, ll l, ll r)
	{
		if(l == r)
		{
			st[id] = node(a[l], a[l], l, l, a[l], a[l], l, l);
			rv[id] = node(-a[l], -a[l], l, l, -a[l], -a[l], l, l);
			return;
		}
		ll mid = (l+r)/2;
		build(id*2, l, mid);
		build(id*2+1, mid+1, r);
		st[id] = merga(st[id*2], st[id*2+1]);
		rv[id] = merga(rv[id*2], rv[id*2+1]);
	}
	void build()
	{
		build(1, 1, n);
	}
	void down(ll id)
	{
		if(!lazy[id])return;
		swap(st[id*2], rv[id*2]);
		swap(st[id*2+1], rv[id*2+1]);
		lazy[id*2] ^= 1;
		lazy[id*2+1] ^= 1;
		lazy[id] = 0;
	}
	void update(ll id, ll l, ll r, ll u, ll v)
	{
		if(u <= l && r <= v)
		{
			swap(st[id], rv[id]);
			lazy[id] ^= 1;
			return;
		}
		if(u > r || l > v)return;
		ll mid = (l+r)/2;
		down(id);
		update(id*2, l, mid, u, v);
		update(id*2+1, mid+1, r, u, v);
		st[id] = merga(st[id*2], st[id*2+1]);
		rv[id] = merga(rv[id*2], rv[id*2+1]);
	}
	void update(ll l, ll r)
	{
		update(1, 1, n, l, r);
	}
};
void sol()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    IT it(n);
    it.build();

    while(k -- > 0)
	{
		if(it.st[1].mx <= 0)break;
		ans += it.st[1].mx;
		it.update(it.st[1].l, it.st[1].r);
	}
	cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".in", "r"))
    {
        freopen(task".in", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
5 4
1 2 1
2 3 4
1 4 3
4 3 2
3
1 3 1
1 3 2
1 3 3
*/

Compilation message (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29