Submission #1057300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057300		TimDee	Floppy (RMI20_floppy)	C++17	100 / 100	65 ms	10444 KiB

floppy

#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;
    vector<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;
        }
        while (a[i]>a[st.back()]) {
            st.pop_back();
            s+="0";
        }
        st.push_back(i);
        s+="1";
    }
    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 (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:110:18: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  110 |     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)
......
  115 |     forn(i,l.size()) {
      |          ~~~~~~~~~~             
floppy.cpp:115:5: note: in expansion of macro 'forn'
  115 |     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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

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