Submission #1057000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057000		TimDee	Floppy (RMI20_floppy)	C++17	52.84 / 100	62 ms	10700 KiB

floppy

#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;

#define forn(i,n) for(int i=0;i<n;++i)
const int maxn=2e5+5;
int l[maxn],r[maxn];
string s;
void dfs(int u, int p) {
    //cout<<"> "<<u<<' '<<p<<' '<<s<<'\n';
    if (l[u]!=-1) {
        if (p==1) s+="00";
        else s+="0";
        dfs(l[u],0);
    }
    if (r[u]!=-1) {
        if (p==0) s+="10";
        else s+="1";
        dfs(r[u],1);
    }
    if (p==0) s+="11";
    if (p==1) s+="01";
}
void read_array(int zzzzz, const vector<int>&a) {
    int n=a.size();
    vector<int> p(n,-1);
    int rt=0;
    forn(i,n) l[i]=r[i]=-1;
    deque<int> st = {0};
    for(int i=1; i<n; ++i) {
        if (a[i]>a[rt]) {
            p[rt]=i;
            rt=i;
            st.clear();
            st.push_back(rt);
            continue;
        }
        if (a[i]<a[st.back()]) {
            p[i]=st.back();
            st.push_back(i);
            continue;
        }
        int last=-1;
        while (a[i]>a[st.back()]) {
            last=st.back();
            st.pop_back();
        }
        p[last]=i;
        p[i]=st.back();
        st.push_back(i);
    }
    forn(i,n) if (i!=rt) {
        if (i<p[i]) l[p[i]]=i;
        else r[p[i]]=i;
    }
    dfs(rt,-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> solve_queries(int zzzzz, int n, const string&s, const vector<int>&l, const vector<int>&r) {
    int m=s.size();
    int d=0;
    vector<int> a;
    int p=0;
    char last;
    string q;
    int from=-1;
    while (s[p]=='1') {
        a.push_back(d);
        q+="1";
        ++d;
        ++p;
    }
    if (!p) {
        q+="0";
        ++d;
        ++p;
    }
    while (p<m) {
        //cout<<"? "<<p<<' '<<d<<" "<<q<<'\n'; cout.flush();
        if (!q.size()) {
            while (s[p]=='1') {
                a.push_back(d);
                q+="1";
                ++d;
                ++p;
            }
        }
        if (s[p]==q.back()) {
            if (s[p]=='1') {
                a.push_back(d);
            }
            q+=s[p];
            ++d;
            ++p;
            from=-1;
        } else {
            if (s[p+1]=='1') {
                if (from!=1) a.push_back(d);
                --d;
                p+=2;
                from=q.back()=='1';
                q.pop_back();
            } else {
                if (s[p]=='1') {
                    a.push_back(d);
                }
                ++d;
                q+=s[p];
                p+=2;
                from=-1;
            }
        }
    }
    if (a.size()<n) a.push_back(0);
    //for(auto&x:a) cout<<x<<' '; cout<<'\n'; exit(0);
    sgt st(n);
    forn(i,n) st.set(i,a[i]);
    vector<int> ans;
    forn(i,l.size()) {
        ans.push_back(st.query(l[i],r[i]+1));
    }
    return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:151:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  151 |     if (a.size()<n) a.push_back(0);
      |         ~~~~~~~~^~
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)
......
  156 |     forn(i,l.size()) {
      |          ~~~~~~~~~~             
floppy.cpp:156:5: note: in expansion of macro 'forn'
  156 |     forn(i,l.size()) {
      |     ^~~~
floppy.cpp:101:10: warning: unused variable 'last' [-Wunused-variable]
  101 |     char last;
      |          ^~~~
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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 24.8446209312 / 72