oj.uz

Submission #442621

# Submission time Handle Problem Language Result Execution time Memory
442621 2021-07-08T10:05:16 Z vanic Meetings (IOI18_meetings) C++14
4 / 100
 5500 ms 122044 KB 
#include "meetings.h"
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;

const int maxn=8e5;

int n, q;
vector < int > h;
ll curr;
int lij;
int des;
vector < ll > sol;
stack < pair < int, int > > s1;
ll sad;

void rekurzija(int x, ll val, stack < pair < int, int > > s2){
	if(x<lij){
		return;
	}
	ll vrij;
	ll pos1, pos2;
	while(!s2.empty() && s2.top().first<h[x]){
		vrij=s2.top().first;
		pos1=s2.top().second;
		s2.pop();
		if(s2.empty()){
			pos2=des+1;
		}
		else{
			pos2=s2.top().second;
		}
		val-=(pos2-pos1)*vrij;
	}
	pos1=x;
	vrij=h[x];
	if(s2.empty()){
		pos2=des+1;
	}
	else{
		pos2=s2.top().second;
	}
	s2.push({h[x], x});
	val+=(pos2-pos1)*vrij;
	rekurzija(x-1, val, s2);
//	cout << sad << ' ' << val << endl;
	curr=min(curr, sad+val);
	while(!s1.empty() && s1.top().first<h[x]){
		vrij=s1.top().first;
		pos1=s1.top().second;
		s1.pop();
		if(s1.empty()){
			pos2=lij-1;
		}
		else{
			pos2=s1.top().second;
		}
		sad-=(pos1-pos2)*vrij;
	}
	pos1=x;
	vrij=h[x];
	if(s1.empty()){
		pos2=lij-1;
	}
	else{
		pos2=s1.top().second;
	}
	s1.push({h[x], x});
	sad+=(pos1-pos2)*vrij;
}


vector < ll > minimum_costs(vector<int> H, vector<int> l, vector<int> r){
	h=H;
	n=h.size();
	q=l.size();
	for(int i=0; i<q; i++){
		lij=l[i];
		des=r[i];
		curr=1e18;
		sad=0;
		while(!s1.empty()){
			s1.pop();
		}
		rekurzija(r[i], 0, {});
		curr=min(curr, sad);
		sol.push_back(curr);
	}
	return sol;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1996 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 5 ms 2252 KB Output is correct
5 Correct 8 ms 2636 KB Output is correct
6 Correct 12 ms 9400 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 6 ms 1868 KB Output is correct
9 Correct 47 ms 10000 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1996 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 5 ms 2252 KB Output is correct
5 Correct 8 ms 2636 KB Output is correct
6 Correct 12 ms 9400 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 6 ms 1868 KB Output is correct
9 Correct 47 ms 10000 KB Output is correct
10 Correct 1490 ms 4532 KB Output is correct
11 Correct 4349 ms 4492 KB Output is correct
12 Correct 1503 ms 4468 KB Output is correct
13 Correct 4504 ms 4596 KB Output is correct
14 Execution timed out 5563 ms 52920 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 5554 ms 122044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 5554 ms 122044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 1996 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 5 ms 2252 KB Output is correct
5 Correct 8 ms 2636 KB Output is correct
6 Correct 12 ms 9400 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 6 ms 1868 KB Output is correct
9 Correct 47 ms 10000 KB Output is correct
10 Correct 1490 ms 4532 KB Output is correct
11 Correct 4349 ms 4492 KB Output is correct
12 Correct 1503 ms 4468 KB Output is correct
13 Correct 4504 ms 4596 KB Output is correct
14 Execution timed out 5563 ms 52920 KB Time limit exceeded
15 Halted 0 ms 0 KB -