oj.uz

Submission #597063

# Submission time Handle Problem Language Result Execution time Memory
597063 2022-07-15T12:50:48 Z ThegeekKnight16 Floppy (RMI20_floppy) C++14
0 / 100
 97 ms 12992 KB 
#include <bits/stdc++.h>
#include <floppy.h>
using namespace std;
const int MAXN = 4e4 + 10;
vector<int> v(MAXN);
struct node
{
    int maxVal, maxId;
    
    node(int Val = -1, int Id = 0) {maxVal = Val; maxId = Id;}
    
    node operator+(node outro)
    {
        node resp;
        resp.maxVal = max(maxVal, outro.maxVal);
        resp.maxId = (maxVal >= outro.maxVal) ? maxId : outro.maxId;
        return resp;
    }
};
node seg[4*MAXN];
 
void build(int pos, int ini, int fim)
{
    if (ini == fim) {seg[pos].maxVal = v[ini]; seg[pos].maxId = ini; return;}
    int m = (ini + fim) / 2;
    int e = 2*pos; int d = 2*pos + 1;
    build(e, ini,  m );
    build(d, m+1, fim);
    seg[pos] = seg[e] + seg[d];
}
 
node query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) {node nulo; return nulo;}
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) / 2;
    int e = 2*pos; int d = 2*pos + 1;
    return query(e, ini, m, p, q) + query(d, m+1, fim, p, q);
}
 
void read_array(int subtask_id, const vector<int> &Nums)
{
    set<int> Valores;
    for (auto Numb : Nums) Valores.insert(Numb);
    map<int, int> Marc; int aux = 1;
    for (auto val : Valores)
    {
        Marc[val] = aux++;
    }
    
    string s = "";
    
    for (int i = 0; i < Nums.size(); i++)
    {
        for (int k = 20; k >= 0; k--) s += (Marc[Nums[i]] & (1 << k)) ? "1" : "0";
    }
    
    save_to_floppy(s);
}
 
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b)
{
    vector<int> v(N+10);
    int j = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int k = 20; k >= 0; k--)
        {
            v[i] += ((bits[j] - '0') << k);
            j++;
        }
    }
    
    build(1, 1, N);
    
    vector<int> resp;
    for (int i = 0; i < a.size(); i++)
    {
        int X = a[i]; int Y = b[i];
        node respQuery = query(1, 1, N, X, Y);
        resp.push_back(respQuery.maxId);
    }
    return resp;
}
 
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
}*/

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < Nums.size(); i++)
      |                     ~~^~~~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     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
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

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

Subtask #3
0.0 / 72.0

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