oj.uz

Submission #1062675

# Submission time Handle Problem Language Result Execution time Memory
1062675 2024-08-17T09:45:39 Z prvocislo Floppy (RMI20_floppy) C++17
7 / 100
 1000 ms 250144 KB 
// Guess who we ran into at the shops?
// Walking in circles like she was lost
// Didn't you hear?
// They called it all off

#include "floppy.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

struct sgt
{
    vector<pair<int, int> > st;
    int n;
    void init(vector<int> v)
    {
        n = v.size();
        st.resize(v.size() * 2);
        for (int i = n; i < 2 * n; i++) st[i] = { v[i - n], i - n };
        for (int i = n - 1; i > 0; i--) st[i] = max(st[i * 2], st[i * 2 + 1]);
    }
    int query(int l, int r)
    {
        pair<int, int> p(-1, -1);
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1) p = max(p, st[l++]);
            if (r & 1) p = max(p, st[--r]);
        }
        return p.second;
    }
};

sgt s;

void make(int l, int r, string& ans)
{
    if (r < l) return;
    int i = s.query(l, r);
    if (l < i) ans.push_back('1');
    else ans.push_back('0');
    if (r > i) ans.push_back('1');
    else ans.push_back('0');
    make(l, i - 1, ans);
    make(i + 1, r, ans);
}

void read_array(int subtask_id, const vector<int> &v) 
{
    s.init(v);
    string ans;
    make(0, v.size() - 1, ans);
    save_to_floppy(ans);
}

int tim = 0; // :) :wave:
int val;
vector<int> v2;
int dfs(int u, const string &b)
{
    int x = val, siz = 1; val--;
    if (b[u * 2] == '1') siz += dfs(u + 1, b);
    v2[tim++] = x;
    if (b[u * 2 + 1] == '1') siz += dfs(u + siz, b);
    return siz;
}

vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b) 
{
    val = n - 1;
    v2.resize(n, -1);
    dfs(0, bits);
    s.init(v2);
    vector<int> ans;
    for (int i = 0; i < a.size(); i++) ans.push_back(s.query(a[i], b[i]));
    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:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < a.size(); i++) ans.push_back(s.query(a[i], b[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 1 ms 820 KB Output is correct
2 Correct 1 ms 820 KB Output is correct
3 Correct 2 ms 820 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 1 ms 1324 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 247592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 250144 KB Time limit exceeded
2 Halted 0 ms 0 KB -