| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1057297 |
2024-08-13T16:39:30 Z |
TimDee |
Floppy (RMI20_floppy) |
C++17 |
|
57 ms |
13616 KB |
#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
void read_array(int zzzzz, const vector<int>&a) {
int n=a.size();
int rt=0;
deque<int> st = {0};
string s="1";
for(int i=1; i<n; ++i) {
if (a[i]>a[rt]) {
rt=i;
while(st.size()) {
s+="0"; st.pop_back();
}
st.push_back(i);
s+="1";
continue;
}
if (a[i]<a[st.back()]) {
st.push_back(i);
s+="1";
continue;
}
while (a[i]>a[st.back()]) {
st.pop_back();
s+="0";
}
st.push_back(i);
s+="1";
}
//cout<<"? "<<s<<'\n'; exit(0);
save_to_floppy(s);
}
struct sgt {
vector<int> t;
vector<int> a;
int sz;
int merge(int i, int j) {
if (i==-1) return j;
if (j==-1) return i;
return a[i]<=a[j]?i:j;
}
sgt(int n) {
sz=1; while (sz<n) sz<<=1; t.assign(2*sz-1,0);
forn(i,n) a.push_back(1e9);
forn(i,n) t[sz-1+i]=i;
}
int query(int v, int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return -1;
if (lx<=l && r<=rx) return t[v];
int m=(l+r)>>1;
return merge(query(2*v+1,l,m,lx,rx),query(2*v+2,m,r,lx,rx));
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
void upd(int v, int l, int r, int i) {
if (r-l==1) return;
int m=(l+r)>>1;
if (i<m) upd(2*v+1,l,m,i);
else upd(2*v+2,m,r,i);
t[v]=merge(t[2*v+1],t[2*v+2]);
}
void set(int i, int x) {
a[i]=x;
upd(0,0,sz,i);
}
};
vector<int> A;
const int maxn=55555;
int l[maxn],r[maxn];
void dfs(int u, int d=0) {
if (u==-1) return;
dfs(l[u],d+1);
A.push_back(d);
dfs(r[u],d+1);
}
vector<int> solve_queries(int zzzzz, int n, const string&s, const vector<int>&l, const vector<int>&r) {
int m=s.size();
vector<int> a;
vector<int> st={0};
vector<int> par(n,-1);
int p=1;
int rt=0;
int nxt=1;
while (p<m) {
int last=-1;
while (s[p]=='0') {
last=st.back();
st.pop_back();
p++;
}
if (last==-1) {
par[nxt]=st.back();
st.push_back(nxt);
++nxt;
} else {
if (last==rt) {
par[rt]=nxt;
st.push_back(nxt);
rt=nxt;
++nxt;
} else {
par[last]=nxt;
par[nxt]=st.back();
st.push_back(nxt);
++nxt;
}
}
++p;
}
forn(i,n) ::l[i]=::r[i]=-1;
forn(i,n) if (i!=rt) if (i<par[i]) ::l[par[i]]=i; else ::r[par[i]]=i;
dfs(rt);
sgt sgt(n);
forn(i,n) sgt.set(i,A[i]);
vector<int> ans;
forn(i,l.size()) {
ans.push_back(sgt.query(l[i],r[i]+1));
}
return ans;
}
Compilation message
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:116:18: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
116 | forn(i,n) if (i!=rt) if (i<par[i]) ::l[par[i]]=i; else ::r[par[i]]=i;
| ^
floppy.cpp:5:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forn(i,n) for(int i=0;i<n;++i)
......
121 | forn(i,l.size()) {
| ~~~~~~~~~~
floppy.cpp:121:5: note: in expansion of macro 'forn'
121 | forn(i,l.size()) {
| ^~~~
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 |
1 ms |
824 KB |
Output is correct |
| 2 |
Correct |
0 ms |
832 KB |
Output is correct |
| 3 |
Correct |
0 ms |
832 KB |
Output is correct |
| 4 |
Correct |
1 ms |
824 KB |
Output is correct |
| 5 |
Correct |
0 ms |
824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
3816 KB |
Output is correct |
| 2 |
Correct |
13 ms |
3780 KB |
Output is correct |
| 3 |
Correct |
13 ms |
4028 KB |
Output is correct |
| 4 |
Correct |
14 ms |
3968 KB |
Output is correct |
| 5 |
Correct |
13 ms |
3776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
12900 KB |
Output is correct |
| 2 |
Correct |
57 ms |
13020 KB |
Output is correct |
| 3 |
Correct |
56 ms |
13616 KB |
Output is correct |
| 4 |
Correct |
56 ms |
13284 KB |
Output is correct |
| 5 |
Correct |
56 ms |
12852 KB |
Output is correct |
