oj.uz

Submission #642630

# Submission time Handle Problem Language Result Execution time Memory
642630 2022-09-20T09:33:10 Z TimDee Floppy (RMI20_floppy) C++17
28 / 100
 47 ms 4244 KB 
#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;

void read_array(int subtask_id, const std::vector<int> &V) {
    vector<int> v=V;
    //if (subtask_id==3) exit(0);
    int n=v.size();
    vector<pair<int,int>> a(n);
    for (int i=0; i<n; ++i) {
        a[i]={v[i],i};
    }
    sort(a.begin(), a.end());
    for (int i=0; i<n; ++i) {
        v[a[i].second]=i;
    }

    int k=log2(n);
    string s;
    for (int i=0; i<n; ++i) {
        string t;
        for (int bit=k; bit>=0; --bit) {
            t+=('0'+((v[i]>>bit)&1));
        }
        s+=t;
    }

    save_to_floppy(s);

}

vector<int> t;
vector<int> A;
int sz=1, neutr; 

int merge (int i, int j) {
    if (A[i]>A[j]) return i;
    else return j;
}

void update(int i, int l, int r) {
    if (r-l==1) return;
    int mid=(l+r)>>1;
    update(2*i+1,l,mid);
    update(2*i+2,mid,r);
    t[i]=merge(t[2*i+1],t[2*i+2]);
}

int query(int i, int l, int r, int lx, int rx) {
    if (l>=rx) return neutr;
    if (r<=lx) return neutr;
    if (l>=lx && r<=rx) return t[i];
    int mid=(l+r)>>1;
    int L=query(2*i+1,l,mid,lx,rx), R=query(2*i+2,mid,r,lx,rx);
    return merge(L,R);
}

int query(int l, int r) {
    return query(0,0,sz,l,r);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    int n=N,m=a.size();
    int k=log2(n); while (sz<n) sz<<=1;
    t.assign(2*sz-1,n);
    string s=bits;
    vector<int> v(n);
    for (int i=0; i<1ll*n*(k+1); i+=k+1) {
        int x=0;
        for (int bit=k; bit>=0; --bit) {
            x+=((s[i+k-bit]=='1')<<bit);
        }
        v[i/(k+1)]=x;
    }
    neutr=n;
    v.push_back(-INT_MAX);
    A=v;
    for (int i=0; i<n; ++i) t[sz-1+i]=i;
    update(0,0,sz);
    vector<int> ans(m,0);
    for (int q=0; q<m; ++q) {
        int l=a[q], r=b[q];
        ans[q]=query(l,r+1);
    }
    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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
3 Correct 2 ms 684 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 2 ms 684 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3424 KB Output is correct
2 Correct 35 ms 4224 KB Output is correct
3 Correct 40 ms 4156 KB Output is correct
4 Correct 47 ms 4188 KB Output is correct
5 Correct 32 ms 4244 KB Output is correct

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 3192 KB L is too large
2 Halted 0 ms 0 KB -