oj.uz

Submission #640835

# Submission time Handle Problem Language Result Execution time Memory
640835 2022-09-15T10:45:15 Z Vladth11 Floppy (RMI20_floppy) C++14
100 / 100
 95 ms 22572 KB 
#include <bits/stdc++.h>
#include "floppy.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
 
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
 
const ll NMAX = 200001;
const ll VMAX = 101;
const ll INF = 2e9;
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 17;
const ll inv2 = 500000004;
 
int stiva[NMAX];
vector <pii> events[NMAX];
 
std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    vector <int> answers(a.size());
    for(int i = 0; i < a.size(); i++){
        events[b[i]].push_back({a[i], i});
    }
    int j = 0, vf = 0;
    for(int i = 0; i < N; i++){
        while(bits[j] == '0'){
            vf--;
            j++;
        }
        stiva[++vf] = i;
        j++;
        for(auto x : events[i]){
            int r = vf, pas = (1 << nr_of_bits);
            while(pas){
                if(r - pas >= 1 && stiva[r - pas] >= x.first){
                    r -= pas;
                }
                pas /= 2;
            }
            answers[x.second] = stiva[r];
        }
    }
    return answers;
}
 
void read_array(int subtask_id, const std::vector<int> &v) {
    stack <int> st;
    string s = "";
    int i = 0;
    for(auto x : v){
        while(st.size() && v[st.top()] < x){
            s += '0';
            st.pop();
        }
        st.push(i);
        i++;
        s += '1';
    }
    save_to_floppy(s);
}

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:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
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 6 ms 10012 KB Output is correct
2 Correct 6 ms 10036 KB Output is correct
3 Correct 6 ms 10092 KB Output is correct
4 Correct 6 ms 10036 KB Output is correct
5 Correct 6 ms 10036 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12272 KB Output is correct
2 Correct 27 ms 12956 KB Output is correct
3 Correct 24 ms 13024 KB Output is correct
4 Correct 25 ms 13008 KB Output is correct
5 Correct 27 ms 12984 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19172 KB Output is correct
2 Correct 89 ms 22572 KB Output is correct
3 Correct 91 ms 22432 KB Output is correct
4 Correct 88 ms 22572 KB Output is correct
5 Correct 91 ms 22564 KB Output is correct