| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805569 |
2023-08-03T17:55:38 Z |
Navas |
Floppy (RMI20_floppy) |
C++14 |
|
64 ms |
11376 KB |
#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<int> p2 = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};
vector<pair<int, int> > st;
string str;
int idididid = -2;
int nnnnn;
void stb(int al, int ar, int x, const vector<int> &v) {
if (al == ar) {
st[x].fi = v[al]+1000000001;
st[x].se = al;
return;
} int m = (al+ar)/2;
stb(al,m,2*x+1,v);
stb(m+1,ar,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 al, int ar, int dl , int dr, int x) {
if (al == dl && ar == dr) {
return st[x];
} int m = (al+ar)/2;
if (dr <= m) {
return ste(al,m,dl,dr,2*x+1);
} else if (dl >= m+1) {
return ste(m+1,ar,dl,dr,2*x+2);
} else {
pair<int, int> a = ste(al,m,dl,m,2*x+1), b = ste(m+1,ar,m+1,dr,2*x+2);
if (a.fi>b.fi) {return a;} else return b;
}
}
void ctb(int al, int ar) {
idididid+=2;
if (al == ar) return;
pair<int, int> ap = ste(0,nnnnn-1,al,ar,0);
if (ap.se == al) {
str[idididid+1]='1';
ctb(ap.se+1,ar);
} else if (ap.se == ar) {
str[idididid]='1';
ctb(al, ap.se-1);
} else {
str[idididid]='1';
str[idididid+1]='1';
ctb(al, ap.se-1);
ctb(ap.se+1,ar);
}
}
void read_array(int subtask_id, const std::vector<int> &v) {
if( subtask_id < 3 )
{
int n = (int)v.size();
std::string bits = "";
vector<pair<int, int> > x;
F(i,0,n) {
x.push_back(make_pair(v[i], i));
}
sort(x.begin(), x.end());
vector<int> k(n);
F(i,0,n) k[x[i].se] = i;
string s;
F(j,0,n) {
for (int i = 13; i>=0; i--) {
if ((k[j] & p2[i]) != 0) {
bits.push_back('1');
} else bits.push_back('0');
}
}
save_to_floppy(bits);
}
else
{
long long n = (long long)v.size(); nnnnn = n;
st.assign(4*n, make_pair(0,0));
str.assign(2*n, '0');
stb(0,n-1,0,v);
ctb(0,n-1);
//cout << str << '\n';
save_to_floppy(str);
}
}
vector<long long> lalala, rarara, papapapa, sub, idx, fir, pth, dth, s2;
void dfs1(long long v, const string &bits) {
if (v != 0) dth[v] = dth[papapapa[v]]+1;
if (str[2*idididid] == '0' && str[2*idididid+1] == '0') { return;}
if (str[2*v] == '1') {
lalala[v] = ++idididid;
papapapa[idididid] = v;
long long k = idididid;
dfs1(k,bits);
sub[v] += sub[k];
}
if (str[2*v+1] == '1') {
rarara[v] = ++idididid;
papapapa[idididid] = v;
long long k = idididid;
dfs1(k,bits);
sub[v] += sub[k];
}
}
void aridir(long long le, long long v) {
idx[v] = le + (lalala[v] != -1 ? sub[lalala[v]] : 0);
if (lalala[v] != -1) {
aridir(le,lalala[v]);
} if (rarara[v] != -1) {
aridir(idx[v]+1, rarara[v]);
} return;
}
void dfs2(long long v) {
pth.push_back(v);
fir[idx[v]]=(long long)pth.size()-1;
if (lalala[v] != -1) {
dfs2(lalala[v]);
pth.push_back(v);
} if (rarara[v] != -1) {
dfs2(rarara[v]);
pth.push_back(v);
} return;
}
void s2b(long long al, long long ar, long long x) {
if (al == ar) {
s2[x] = pth[al];
return;
} long long 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];
}
long long s2e (long long al, long long ar, long long dl, long long dr, long long x) {
if (al == dl && ar == dr) {
return s2[x];
} long long 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 {
long long 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) {
if( subtask_id < 3 )
{
st.resize(4*N);
int m = (int)a.size();
vector<int> v(N, 0);
std::vector<int> ans;
F(i,0,N) {
F(j,0,14) {
if (bits[14*i+j] == '1') v[i] += p2[13-j];
}
}
stb(0,N-1,0,v);
F(i,0,m) {
ans.push_back(ste(0,N-1,a[i],b[i],0).se);
}
return ans;
}
else
{
vector<int> ans;
long long m = (long long)a.size();
lalala.assign(N, -1); rarara.assign(N,-1); papapapa.assign(N,-1); sub.assign(N,1); idx.assign(N,0); dth.assign(N,0); fir.assign(N,0);
idididid = 0;
dfs1(0, bits);
aridir(0, 0);
dfs2(0);
//F(i,0,N) cout << idx[i] << " " << idx[lalala[i]] << " " << idx[rarara[i]] << " " << idx[papapapa[i]] << " " << sub[i] << " " << dth[i] << '\n';
long long ps = (long long)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 |
Correct |
3 ms |
788 KB |
Output is correct |
| 2 |
Correct |
2 ms |
804 KB |
Output is correct |
| 3 |
Correct |
2 ms |
804 KB |
Output is correct |
| 4 |
Correct |
2 ms |
812 KB |
Output is correct |
| 5 |
Correct |
2 ms |
812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
3604 KB |
Output is correct |
| 2 |
Correct |
27 ms |
4408 KB |
Output is correct |
| 3 |
Correct |
26 ms |
4376 KB |
Output is correct |
| 4 |
Correct |
28 ms |
4300 KB |
Output is correct |
| 5 |
Correct |
28 ms |
4524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
11376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
