#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
#define F(i,s,e) for (int i = s; i<e; i++)
#define fi first
#define se second
#include "floppy.h"
using namespace std;
vector<pair<int, int> > st;
string str;
int id = -2;
int _n;
void stb(int l, int r, int x, const vector<int> &v) {
if (l == r) {
st[x].fi = v[l];
st[x].se = l;
return;
} int m = (l+r)/2;
stb(l,m,2*x+1,v);
stb(m+1,r,2*x+2,v);
if (st[2*x+1].fi > st[2*x+2].fi) {
st[x] = st[2*x+1];
} else {
st[x] = st[2*x+2];
}
}
pair<int, int> ste(int l, int r, int dl , int dr, int x) {
if (l == dl && r == dr) {
return st[x];
} int m = (l+r)/2;
if (dr <= m) {
return ste(l,m,dl,dr,2*x+1);
} else if (dl >= m+1) {
return ste(m+1,r,dl,dr,2*x+2);
} else {
pair<int, int> a = ste(l,m,dl,m,2*x+1), b = ste(m+1,r,m+1,dr,2*x+2);
if (a.fi>b.fi) {return a;} else return b;
}
}
void ctb(int l, int r) {
id+=2;
if (l == r) return;
pair<int, int> p = ste(0,_n-1,l,r,0);
if (p.se == l) {
str[id+1]='1';
ctb(p.se+1,r);
} else if (p.se == r) {
str[id]='1';
ctb(l, p.se-1);
} else {
str[id]='1';
str[id+1]='1';
ctb(l, p.se-1);
ctb(p.se+1,r);
}
}
void read_array(int subtask_id, const std::vector<int> &v) {
int n = (int)v.size(); _n = n;
st.assign(4*n, make_pair(0,0));
str.assign(2*n, '0');
stb(0,n-1,0,v);
ctb(0,n-1);
save_to_floppy(str);
}
vector<int> l, r, p, sub, idx, fir, pth, dth, s2;
void dfs1(int v, const string &bits) {
if (v != 0) dth[v] = dth[p[v]]+1;
if (str[2*id] == '0' && str[2*id+1] == '0') { return;}
if (str[2*v] == '1') {
l[v] = ++id;
p[id] = v;
int k = id;
dfs1(k,bits);
sub[v] += sub[k];
}
if (str[2*v+1] == '1') {
r[v] = ++id;
p[id] = v;
int k = id;
dfs1(k,bits);
sub[v] += sub[k];
}
}
void aid(int le, int v) {
idx[v] = le + (l[v] != -1 ? sub[l[v]] : 0);
if (l[v] != -1) {
aid(le,l[v]);
} if (r[v] != -1) {
aid(idx[v]+1, r[v]);
} return;
}
void dfs2(int v) {
pth.push_back(v);
fir[idx[v]]=(int)pth.size()-1;
if (l[v] != -1) {
dfs2(l[v]);
pth.push_back(v);
} if (r[v] != -1) {
dfs2(r[v]);
pth.push_back(v);
} return;
}
void s2b(int al, int ar, int x) {
if (al == ar) {
s2[x] = pth[al];
return;
} int m = (al+ar)/2;
s2b(al,m,2*x+1);
s2b(m+1,ar,2*x+2);
if (dth[s2[2*x+1]] < dth[s2[2*x+2]]) {
s2[x] = s2[2*x+1];
}else s2[x] = s2[2*x+2];
}
int s2e (int al, int ar, int dl, int dr, int x) {
if (al == dl && ar == dr) {
return s2[x];
} int m = (al+ar)/2;
if (dr <= m) {
return s2e(al, m, dl, dr, 2*x+1);
} else if (dl >= m+1) {
return s2e( m+1, ar, dl, dr, 2*x+2);
} else {
int a = s2e(al, m, dl, m, 2*x+1), b = s2e( m+1, ar, m+1, dr, 2*x+2);
if (dth[a] < dth[b]) {
return a;
} else return b;
}
}
std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
vector<int> ans;
int m = (int)a.size();
l.assign(N, -1); r.assign(N,-1); p.assign(N,-1); sub.assign(N,1); idx.assign(N,0); dth.assign(N,0); fir.assign(N,0);
id = 0;
dfs1(0, bits);
aid(0, 0);
dfs2(0);
//F(i,0,N) cout << idx[i] << " " << idx[l[i]] << " " << idx[r[i]] << " " << idx[p[i]] << " " << sub[i] << " " << dth[i] << '\n';
int ps = (int)pth.size();
s2.assign(4*ps, 0);
s2b(0, ps-1, 0);
//F(i,0,N) cout << fir[idx[i]] << " ";
F(i,0,m) {
ans.push_back(idx[s2e(0,ps-1,min(fir[a[i]], fir[b[i]]),max(fir[a[i]], fir[b[i]]),0)]);
//cout << ans[i] << " ";
}
return ans;
}
Compilation message
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 |
2 ms |
800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
3724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
13684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
