| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 642895 |
2022-09-20T17:34:34 Z |
lis05st |
Floppy (RMI20_floppy) |
C++17 |
|
129 ms |
21192 KB |
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX=2e5;
int ARR[NMAX+5],L[NMAX+5],R[NMAX+5],pr[NMAX+5];
string floppy;
vector<int>vec;
void dfs(int v){
floppy+='0'+(L[v]==-1?0:1);
floppy+='0'+(R[v]==-1?0:1);
if(L[v]!=-1)dfs(L[v]);
vec.push_back(ARR[v]);
if(R[v]!=-1)dfs(R[v]);
}
int sL[NMAX+5],sR[NMAX+5],spr[20][NMAX+5];
int TIME=1,ID=0;
vector<int>arr;
int dfs2(string&s){
bool haveLeft=s[ID]=='1';
bool haveRight=s[ID+1]=='1';
ID+=2;
if(haveLeft){
int x=dfs2(s);
sL[TIME]=x;
spr[0][x]=TIME;
}
int v=TIME;
arr.push_back(v);
spr[0][v]=v;
TIME++;
if(haveRight){
int x=dfs2(s);
sR[v]=x;
spr[0][x]=v;
}
return v;
}
int tin[NMAX+5],tout[NMAX+5];
int T=0;
void dfs3(int v,int d){
if(v==-1)return;
tin[v]=++T;
for(int lvl=1;lvl<=19;lvl++)spr[lvl][v]=spr[lvl-1][spr[lvl-1][v]];
dfs3(sL[v],d+1);
dfs3(sR[v],d+1);
tout[v]=++T;
}
int restore(string s){
memset(sL,-1,sizeof sL);
memset(sR,-1,sizeof sR);
int root=dfs2(s);
return root;
}
bool aprofb(int a,int b){
if(tin[a]<=tin[b]&&tout[b]<=tout[a])return 1;
return 0;
}
int lca(int a,int b){
if(aprofb(a,b))return a;
if(aprofb(b,a))return b;
//cout<<"LCA "<<a<<" "<<b<<"\n";
for(int lvl=19;lvl>=0;lvl--){
//cout<<lvl<<" "<<a<<" "<<b<<"\n";
//cout<<spr[lvl][a]<<"\n";
if(!aprofb(spr[lvl][a],b))a=spr[lvl][a];
}
return spr[0][a];
}
void read_array(int subtask_id, const std::vector<int> &v) {
map<int,int>mp;
vector<int>vec2;
vector<int>v2=v;
for(auto e:v)vec2.push_back(e);
sort(vec2.begin(),vec2.end());
for(int i=0;i<v.size();i++)mp[vec2[i]]=i;
for(auto&e:v2)e=mp[e];
int n=v.size();
for(int i=1;i<=n;i++)ARR[i]=v2[i-1];
int root=1;
L[root]=-1;
R[root]=-1;
pr[root]=-1;
for(int i=2;i<=n;i++){
L[i]=R[i]=-1;
int last=i-1;
while(last!=root&&ARR[last]<ARR[i])last=pr[last];
if(ARR[last]<ARR[i]){
root=i;
L[i]=last;
pr[last]=i;
}
else if(R[last]==-1){
R[last]=i;
pr[i]=last;
}else{
pr[i]=last;
pr[R[last]]=i;
L[i]=R[last];
R[last]=i;
}
}
dfs(root);
save_to_floppy(floppy);
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
string ss=bits;
int root=restore(ss);
assert(root!=-1);
assert(arr.size()==N);
dfs3(root,0);
int n=bits.size()/2;
std::vector<int> answers = vector<int>(a.size(),0);
for(int i=0;i<a.size();i++)answers[i]=lca(a[i]+1,b[i]+1)-1;
return answers;
}
Compilation message
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<v.size();i++)mp[vec2[i]]=i;
| ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from floppy.cpp:5:
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:123:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
123 | assert(arr.size()==N);
| ~~~~~~~~~~^~~
floppy.cpp:127:18: 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<a.size();i++)answers[i]=lca(a[i]+1,b[i]+1)-1;
| ~^~~~~~~~~
floppy.cpp:125:9: warning: unused variable 'n' [-Wunused-variable]
125 | int n=bits.size()/2;
| ^
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 |
2 ms |
2460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2476 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2476 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2472 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
5728 KB |
Output is correct |
| 2 |
Correct |
27 ms |
6580 KB |
Output is correct |
| 3 |
Correct |
25 ms |
6804 KB |
Output is correct |
| 4 |
Correct |
27 ms |
6948 KB |
Output is correct |
| 5 |
Correct |
32 ms |
6620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
16308 KB |
Output is correct |
| 2 |
Correct |
129 ms |
19836 KB |
Output is correct |
| 3 |
Correct |
107 ms |
21192 KB |
Output is correct |
| 4 |
Correct |
111 ms |
21084 KB |
Output is correct |
| 5 |
Correct |
114 ms |
19984 KB |
Output is correct |
