Submission #584987

#	Time	Username	Problem	Language	Result	Execution time	Memory
584987		keta_tsimakuridze	Discharging (NOI20_discharging)	C++14	49 / 100	621 ms	85264 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 1e6 + 5, mod = 1e9 + 7, inf = mod; //!
int t, pos[N], a[N], bef[N];
map<int,int> id;
int f(int k,int x,int l) {
	return k * x + l;
}
pii tree[4 * N];
void insert(int u,int l,int r, int k,int b) {
	if(l == r) {
		if(f(k, pos[l], b) < f(tree[u].f, pos[l], b)) tree[u] = {k, b};
		return;
	}
	int mid = (l + r) / 2;
	if(k < tree[u].f) {
		swap(k, tree[u].f);
		swap(b, tree[u].s);
	}
	if(f(k, pos[mid], b) <= f(tree[u].f, pos[mid], tree[u].s)) {
		insert(2 * u + 1, mid + 1, r, tree[u].f, tree[u].s);
		tree[u].f = k; tree[u].s = b;
		return;
	}
	insert(2 * u, l, mid, k, b);
}
int get(int u,int l,int r,int id) {
	if(l > id || r < id) return inf;
	if(l == r) {
		return f(tree[u].f, pos[l], tree[u].s);
	}
	int mid = (l + r) / 2;
	return min(f(tree[u].f, pos[id], tree[u].s), min(get(2 * u, l, mid, id), get(2 * u + 1, mid + 1,r, id)));
}
main() {
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n;
	cin >> n;
	vector<int> x;
	int mx = 0;
	x.push_back(0);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(a[i] > mx) {
			bef[x.size()] = i - 1;
			x.push_back(i);
			mx = a[i];
			
		}
	}
	bef[x.size()] = n;
	for(int i = 0; i < x.size(); i++) {
		id[x[i]] = i;
		pos[i] = a[x[i]];
	}
	int ANS = 0;
	for(int i = 1; i < x.size(); i++) {
		
		int ans = get(1, 1, x.size() - 1, i) + n * a[x[i]];	
		//cout << i << " __ " <<  get(1, 1, x.size() - 1, i) << " " << (n - bef[i]) * a[x[i]] << " " << ans << endl;
		insert(1, 1, x.size() - 1, -bef[i + 1], ans);
	
		if(i + 1 == x.size()) ANS = ans;

	}
	cout << ANS;
	
	
}

Compilation message (stderr)

Discharging.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~
Discharging.cpp: In function 'int main()':
Discharging.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
Discharging.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
Discharging.cpp:68:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(i + 1 == x.size()) ANS = ans;
      |      ~~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28