oj.uz

Submission #115915

# Submission time Handle Problem Language Result Execution time Memory
115915 2019-06-09T20:47:55 Z claudy Meetings (IOI18_meetings) C++14
60 / 100
 5500 ms 64480 KB 
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/// LONG LONG BAGA

int t[1 << 22],a[1 << 20],nxt[2][1 << 20],n;


void upd(int nod,int l,int r,int pos,int val)
{
	if(l == r)
	{
		t[nod] = val;
		return ;
	}
	int mid = l + r >> 1;
	if(pos <= mid) upd(nod << 1,l,mid,pos,val);
	else upd(nod << 1 | 1,mid + 1,r,pos,val);
	t[nod] = min(t[nod << 1],t[nod << 1 | 1]);
}

int qry(int nod,int tl,int tr,int l,int r)
{
	if(l > r) return 1e18 + 1;
	if(l == tl && tr == r) return t[nod];
	int mid = tl + tr >> 1;
	return min(qry(nod << 1,tl,mid,l,min(mid,r)),qry(nod << 1 | 1,mid + 1,tr,max(mid + 1,l),r));
}

int calcleft(int idx,int f)
{
	if(f == 0) return 0;
	int ans = 0;
	while(idx)
	{
		if(idx > f && nxt[0][idx] <= f)
		{
			ans += a[idx] * (f - nxt[0][idx]);
		}
		else if(idx <= f)
		{
			ans += a[idx] * (idx - nxt[0][idx]);
		}
		idx = nxt[0][idx];
	}
	return ans;
}

int calright(int idx,int f)
{
	if(f == n + 1) return 0;
	int ans = 0;
	while(idx != n + 1)
	{
		if(idx < f && nxt[1][idx] >= f)
		{
			ans += a[idx] * (nxt[1][idx] - f);
		}
		else if(idx >= f)
		{
			ans += a[idx] * (nxt[1][idx] - idx);
		}
		idx = nxt[1][idx];
	}
	return ans;
}

int Q(int l,int r)
{
	set<int>ms;
	ms.insert(l);
	ms.insert(r);
	ms.insert(r + 1);
	int idx = nxt[1][l];
	while(idx < r)
	{
		ms.insert(idx);
		idx = nxt[1][idx];
	}
	idx = nxt[0][r];
	while(idx >= l)
	{
		ms.insert(idx + 1);
		idx = nxt[0][idx];
	}
	int ans = 1e18;
	vector<int>vec;
	for(auto it : ms) vec.pb(it);
	for(int i = 0;i < sz(vec) - 1;i++)
	{
		int L = calcleft(vec[i],l - 1);
		int R = calright(vec[i],r + 1);
		ans = min(ans,qry(1,1,n,vec[i],vec[i + 1] - 1) - L - R);
	}
	return ans;
}

#undef int
vector<ll>minimum_costs(vector<int>H, vector<int>L, vector<int>R)
#define int ll
{
	n = sz(H);
	for(int i = 1;i <= n;i++) 
	{
		a[i] = H[i - 1];
	}
	stack<int>st;
	st.push(0);
	a[0] = 1e9 + 1;
	for(int i = 1;i <= n;i++)
	{
		while(a[st.top()] <= a[i])
		{
			st.pop();
		}
		nxt[0][i] = st.top();
		st.push(i);
	}
	while(sz(st)) st.pop();
	st.push(n + 1);
	a[n + 1] = 1e9 + 1;
	for(int i = n;i >= 1;i--)
	{
		while(a[st.top()] <= a[i])
		{
			st.pop();
		}
		nxt[1][i] = st.top();
		st.push(i);
	}
	for(int i = 1;i <= 4 * n;i++) t[i] = 1e18 + 1;
	for(int i = 1;i <= n;i++)
	{
		int x = 0;
		int idx = i;
		while(idx)
		{
			x += (idx - nxt[0][idx]) * a[idx];
			idx = nxt[0][idx];
		}
		idx = i;
		while(idx != n + 1)
		{
			x += (nxt[1][idx] - idx) * a[idx];
			idx = nxt[1][idx];
		}
		x -= a[i];
		upd(1,1,n,i,x);
	}
	vector<int>ans;
	for(int i = 0;i < sz(L);i++)
	{
		L[i]++;
		R[i]++;
		ans.pb(Q(L[i],R[i]));
	}
	return ans;
}

/*
int32_t main(){_
	//freopen("input","r",stdin);

	return 0;
}*/

Compilation message

meetings.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")
 
meetings.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
meetings.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
meetings.cpp: In function 'long long int qry(long long int, long long int, long long int, long long int, long long int)':
meetings.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 3 ms 548 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 32 ms 904 KB Output is correct
11 Correct 23 ms 860 KB Output is correct
12 Correct 28 ms 860 KB Output is correct
13 Correct 20 ms 904 KB Output is correct
14 Correct 11 ms 860 KB Output is correct
15 Correct 27 ms 880 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 85 ms 2284 KB Output is correct
3 Correct 245 ms 10072 KB Output is correct
4 Correct 304 ms 10100 KB Output is correct
5 Correct 140 ms 10068 KB Output is correct
6 Correct 211 ms 10096 KB Output is correct
7 Correct 232 ms 10056 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 85 ms 2284 KB Output is correct
3 Correct 245 ms 10072 KB Output is correct
4 Correct 304 ms 10100 KB Output is correct
5 Correct 140 ms 10068 KB Output is correct
6 Correct 211 ms 10096 KB Output is correct
7 Correct 232 ms 10056 KB Output is correct
8 Correct 465 ms 10060 KB Output is correct
9 Correct 288 ms 10196 KB Output is correct
10 Correct 444 ms 10196 KB Output is correct
11 Correct 548 ms 10228 KB Output is correct
12 Correct 346 ms 10220 KB Output is correct
13 Correct 501 ms 10180 KB Output is correct
14 Correct 230 ms 10224 KB Output is correct
15 Correct 1000 ms 10260 KB Output is correct
16 Correct 515 ms 10196 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 532 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 3 ms 548 KB Output is correct
10 Correct 32 ms 904 KB Output is correct
11 Correct 23 ms 860 KB Output is correct
12 Correct 28 ms 860 KB Output is correct
13 Correct 20 ms 904 KB Output is correct
14 Correct 11 ms 860 KB Output is correct
15 Correct 27 ms 880 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 85 ms 2284 KB Output is correct
18 Correct 245 ms 10072 KB Output is correct
19 Correct 304 ms 10100 KB Output is correct
20 Correct 140 ms 10068 KB Output is correct
21 Correct 211 ms 10096 KB Output is correct
22 Correct 232 ms 10056 KB Output is correct
23 Correct 465 ms 10060 KB Output is correct
24 Correct 288 ms 10196 KB Output is correct
25 Correct 444 ms 10196 KB Output is correct
26 Correct 548 ms 10228 KB Output is correct
27 Correct 346 ms 10220 KB Output is correct
28 Correct 501 ms 10180 KB Output is correct
29 Correct 230 ms 10224 KB Output is correct
30 Correct 1000 ms 10260 KB Output is correct
31 Correct 515 ms 10196 KB Output is correct
32 Execution timed out 5575 ms 64480 KB Time limit exceeded
33 Halted 0 ms 0 KB -