I am trying to solve this problem but getting TLE.
Can you please give any hints after checking the code?
I am using a queue and deque to have O(1) (amortized) in push, pop and getMax.
Still I am getting TLE. Any help is appreciated.
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
/* a=target variable, b=bit number to act upon 0-n */
define BIT_SET(a,b) ((a) |= (1<<(b)))
define BIT_CLEAR(a,b) ((a) &= ~(1<<(b)))
define BIT_FLIP(a,b) ((a) ^= (1<<(b)))
define BIT_CHECK(a,b) ((a) & (1<<(b)))
/* x=target variable, y=mask */
define BITMASK_SET(x,y) ((x) |= (y))
define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
define BITMASK_FLIP(x,y) ((x) ^= (y))
define BITMASK_CHECK(x,y) ((x) & (y))
using namespace std;
typedef unsigned long long int ull;
typedef unsigned long int ul;
typedef long long int ll;
typedef long int li;
typedef unsigned int ui;
//
// two solutions exists
// 1. Using two stacks
// 2. Using a queue and a deque (double ended queue not priority queue)
// using priority queue will cause the order to be O(nlogn) which is not good
// with options 1 or 2 amortized complexity is O(n) which is better than pq.
//
// 2. Using queue and deque
class MaxQ {
public:
queue q;
deque dq;
MaxQ () {}
void push(int val) {
if (q.empty()) {
q.push(val);
dq.push_back(val);
} else {
q.push(val);
while (!dq.empty() && dq.back() < val)
dq.pop_back();
dq.push_back(val);
}
}
void pop() {
if (q.empty() || dq.empty())
return;
if (q.front() == dq.front())
dq.pop_front();
q.pop();
}
int getMax() {
if (!dq.empty())
return dq.front();
return 0;
}
};
int main() {
int n;
scanf("%d",&n);
int v[n];
for (int i = 0; i < n; i++)
scanf("%d",&v[i]);
for (int k = 1; k <= n; k++) {
int ans = 0;
MaxQ Q;
for (int i = 0; i < k; i++) {
Q.push(v[i]);
}
ans += Q.getMax();
for (int i = k; i < n; i++) {
Q.pop();
Q.push(v[i]);
ans += Q.getMax();
}
printf("%d\n",ans);
}
}
if 0
int main(){
int n;
scanf("%d",&n);
vector <int> v (n, 0);
for (int i = 0; i < n; i++) {
scanf("%d",&v[i]);
}
for (int k = 1; k <= n; k++) {
// for each k
int ans = 0;
priority_queue <pair <int, int>, vector <pair <int, int> >, less <pair<int,int> > > pq;
for (int i = 0; i < k; i++) {
pq.push(make_pair(v[i],i));
}
ans += (pq.empty() ? 0 : pq.top().first);
//printf("adding: %d\n",pq.top().first);
for (int i = k; i < v.size(); i++) {
while (!pq.empty() && pq.top().second <= (i-k))
pq.pop();
pq.push(make_pair(v[i],i));
//printf("adding: %d\n", pq.top().first);
ans += (pq.empty() ? 0 : pq.top().first);
}
printf("%d\n",ans);
}
return 0;
}
endif