oj.uz

Submission #485985

# Submission time Handle Problem Language Result Execution time Memory
485985 2021-11-10T03:44:46 Z Killer2501 Feast (NOI19_feast) C++14
41 / 100
 35 ms 22596 KB 
#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 = 2e5+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], c[20][20], d[N], h[N], P[N][20], dp[N];
vector<ll> adj[N], g[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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 22568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 22596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9764 KB Output is correct
4 Correct 7 ms 9768 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 7 ms 9676 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9764 KB Output is correct
4 Correct 7 ms 9768 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 7 ms 9676 KB Output is correct
11 Correct 6 ms 9804 KB Output is correct
12 Correct 6 ms 9804 KB Output is correct
13 Correct 6 ms 9804 KB Output is correct
14 Correct 6 ms 9804 KB Output is correct
15 Correct 5 ms 9804 KB Output is correct
16 Correct 5 ms 9804 KB Output is correct
17 Correct 5 ms 9804 KB Output is correct
18 Correct 5 ms 9804 KB Output is correct
19 Correct 6 ms 9804 KB Output is correct
20 Correct 5 ms 9804 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9764 KB Output is correct
4 Correct 7 ms 9768 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 7 ms 9676 KB Output is correct
11 Correct 6 ms 9804 KB Output is correct
12 Correct 6 ms 9804 KB Output is correct
13 Correct 6 ms 9804 KB Output is correct
14 Correct 6 ms 9804 KB Output is correct
15 Correct 5 ms 9804 KB Output is correct
16 Correct 5 ms 9804 KB Output is correct
17 Correct 5 ms 9804 KB Output is correct
18 Correct 5 ms 9804 KB Output is correct
19 Correct 6 ms 9804 KB Output is correct
20 Correct 5 ms 9804 KB Output is correct
21 Correct 8 ms 10700 KB Output is correct
22 Correct 6 ms 10700 KB Output is correct
23 Correct 6 ms 10760 KB Output is correct
24 Correct 6 ms 10700 KB Output is correct
25 Correct 6 ms 10828 KB Output is correct
26 Correct 7 ms 10828 KB Output is correct
27 Correct 6 ms 10828 KB Output is correct
28 Correct 7 ms 10828 KB Output is correct
29 Correct 6 ms 10760 KB Output is correct
30 Correct 7 ms 10700 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 22568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -