oj.uz

Submission #596587

# Submission time Handle Problem Language Result Execution time Memory
596587 2022-07-14T21:17:31 Z ThegeekKnight16 Floppy (RMI20_floppy) C++14
0 / 100
 1000 ms 18776 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 k = 1;
    for (auto val : Valores)
    {
        Marc[val] = k++;
    }
    
    string s = "";
    for (int i = Nums.size(); i >= 1; i--)
    {
        for (int j = 0; j < Nums.size(); j++) s += (Marc[Nums[j]] == i) ? "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 = N; i >= 1; i--)
    {
        for (int count = 1; count <= N; count++)
        {
            if (bits[j] == '1')  v[count] = i;
            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:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int j = 0; j < Nums.size(); j++) s += (Marc[Nums[j]] == i) ? "1" : "0";
      |                         ~~^~~~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     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 9 ms 4144 KB L is too large
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 18776 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 1092 ms 15044 KB Time limit exceeded
2 Halted 0 ms 0 KB -