#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define en cout << '\n'
#define pi pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
struct Fenwick{
vector<int> t;
int n;
Fenwick(int n): n(n){
t.resize(n+1);
}
void add(int v){
while(v <= n){
t[v]++;
v += v&-v;
}
}
int get(int v){
int res = 0;
while(v > 0){
res += t[v];
v -= v&-v;
}
return res;
}
};
void op(vector<int> &a, vector<int> &A, vector<int> &B){
if(a.size() <= 1){
A = a;
B.pb(0);
return;
}
A.pb(a[0]);
A.pb(a[1]);
B.pb(0);
B.pb(1);
for(int i = 2; i < a.size(); ++i){
if(a[i] > A.back() && A.back() > A[int(A.size()) - 2]){
A.pop_back();
B.pop_back();
A.pb(a[i]);
B.pb(i);
}else if(a[i] < A.back() && A.back() < A[int(A.size()) - 2]){
A.pop_back();
B.pop_back();
A.pb(a[i]);
B.pb(i);
}else{
A.pb(a[i]);
B.pb(i);
}
}
}
int n;
vector<int> A, B, A2, A1, B1, B2, a;
Fenwick f(1000000);
void init(int nn, std::vector<int> aa) { n=nn;a=aa;
if(n == 1) return;
op(a, A, B);
// elimizde a b var cool
// if(A[0] > A[1]){
// for(int i = 0; i < A.size(); i += 2){
// f.add(B[i]);
// }
// }else{
// for(int i = 1; i < A.size(); i += 2){
// f.add(B[i]);
// }
// }
for(int i = 1; i + 1 < n; ++i){
if(a[i] > a[i - 1] && a[i] > a[i + 1]) f.add(i + 1);
}
}
int max_towers(int L, int R, int D) { ++L, ++R;
if(n == 1 || L == R) return 1;
--L, --R;
vector<int> X;
for(int i = L; i <= R; ++i) X.pb(a[i]);
A.clear();
B.clear();
op(X, A, B);
// set<pair<int, int>> s;
// priority_queue<pair<int, int>> q;
// for(int i = 0; i < A.size(); ++i){
// s.insert({i, A[i]});
// if(i > 0 && i + 1 < A.size()){
// if(A < )
// q.push({-min(A[i + 1] - A[i], A[i - 1] - A[i]), i});
// }
// }
bool ok = 1;
while(ok){
ok = 0;
if(A.size() == 1) return 1;
int mindif = 1000000000, pos = -1;
for(int i = 0; i < A.size(); ++i){
if(i + 1 < A.size() && A[i] < A[i + 1]){
if(mindif > A[i + 1] - A[i]){
mindif = A[i + 1] - A[i];
pos = i;
}
}
if(i > 0 && A[i] < A[i - 1]){
if(mindif > A[i - 1] - A[i]){
mindif = A[i - 1] - A[i];
pos = i;
}
}
}
if(pos == -1) break;
if(mindif < D)
A.erase(A.begin() + pos), ok = 1;
else
break;
for(int i = 0; i + 2 < A.size(); ++i){
if(A[i] < A[i + 1] && A[i + 1] < A[i + 2]){
A.erase(A.begin() + i + 1);
--i;
continue;
}
if(A[i] > A[i + 1] && A[i + 1] > A[i + 2]){
A.erase(A.begin() + i + 1);
--i;
continue;
}
}
}
// for(auto k: A) cout << k<< ' ';
int ans = 0;
for(int i = 1; i + 1 < A.size(); ++i){
if(A[i] > A[i - 1] && A[i] > A[i + 1] ) ++ans;
}
return max(ans+1,1);
}
Compilation message
towers.cpp: In function 'void op(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
towers.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 2; i < a.size(); ++i){
| ~~^~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0; i < A.size(); ++i){
| ~~^~~~~~~~~~
towers.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if(i + 1 < A.size() && A[i] < A[i + 1]){
| ~~~~~~^~~~~~~~~~
towers.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0; i + 2 < A.size(); ++i){
| ~~~~~~^~~~~~~~~~
towers.cpp:142:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i = 1; i + 1 < A.size(); ++i){
| ~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4088 ms |
5436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4184 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
4184 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4184 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
4184 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4040 ms |
6660 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4059 ms |
4952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4184 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
4184 KB |
1st lines differ - on the 1st token, expected: '34', found: '33' |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4088 ms |
5436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
