#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> ii;
struct node {
node *lf, *rg;
int l, r, val;
node(int x, int y): l(x), r(y) {}
void build(vector<int> v) {
if (l == r) {
val = v[l];
return;
}
int mid = (l+r)/2;
lf = new node(l,mid); lf->build(v);
rg = new node(mid+1,r); rg->build(v);
val = max(lf->val,rg->val);
}
ii query(int x, int y) {
if (l > y || r < x) return ii(-1,-1);
if (l >= x && r <= y) return ii(val,l);
return max(lf->query(x,y),rg->query(x,y));
}
} *st;
vector<int> compress(vector<int> v) {
vector<int> tmp, res;
map<int,int> num;
tmp = v;
sort(tmp.begin(),tmp.end());
tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
for (int i = 0; i < tmp.size(); i++) num[tmp[i]] = i;
for (auto i : v) res.push_back(num[i]);
return res;
}
void read_array(int subtask_id, const vector<int> &v) {
string bits;
stack<int> s;
vector<int> val;
val = compress(v);
for (auto i : val) {
while (!s.empty() && s.top() < i) {
bits += '0';
s.pop();
}
bits += '1';
s.push(i);
}
// cout << bits << '\n';
save_to_floppy(bits);
}
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &l, const vector<int> &r) {
stack<int> s;
vector<int> val(N,-1), ls(N), res;
for (int i = 0, j = 0; i < bits.length(); i++) {
if (bits[i] == '1') {
if (s.empty()) ls[j] = j;
else ls[j] = s.top();
s.push(j++);
}
else s.pop();
}
for (int i = N-1, j = N-1; i >= 0; i--) {
if (!i || ls[i-1] != ls[i]) val[i] = j--;
}
for (int i = 0, j = 0; i < N; i++) {
if (val[i] == -1) val[i] = j++;
}
st = new node(0,N-1); st->build(val);
for (int i = 0; i < l.size(); i++) {
auto ans = st->query(l[i],r[i]);
res.push_back(ans.se);
}
return res;
}
Compilation message
floppy.cpp: In function 'std::vector<int> compress(std::vector<int>)':
floppy.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < tmp.size(); i++) num[tmp[i]] = i;
| ~~^~~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:67:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0, j = 0; i < bits.length(); i++) {
| ~~^~~~~~~~~~~~~~~
floppy.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < l.size(); i++) {
| ~~^~~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
101 | if (query_answers.size() != M) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1137 ms |
18236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
