oj.uz

Submission #1003663

# Submission time Handle Problem Language Result Execution time Memory
1003663 2024-06-20T14:52:18 Z thelepi Radio (COCI22_radio) C++17
10 / 110
 177 ms 309452 KB 
#include <iostream>
#include <string>
#include <cassert>
#include <vector>

using namespace std;

struct node{
  bool collision = false;
  vector<int> factors;
};

node segtree[4000005];
vector<int> primefactors[1000001];

node merge(node a, node b){
  if(a.collision || b.collision)
    return node{true, vector<int>()};
  if(a.factors.size() == 0)
    return b;
  if(b.factors.size() == 0)
    return a;
  vector<int> merged;
  int i = 0, j = 0;
  while(i < a.factors.size() || j < b.factors.size()){
    if(i == a.factors.size()){
      merged.push_back(b.factors[j]);
      j++;
      continue;
    }
    if(i == b.factors.size()){
      merged.push_back(a.factors[i]);
      i++;
      continue;
    }
    if(a.factors[i] == b.factors[j]){
      return node{true, vector<int>()};
    }
    if(a.factors[i] < b.factors[j]){
      merged.push_back(a.factors[i]);
      i++;
    } else {
      merged.push_back(b.factors[j]);
      j++;
    }
  }
  return node{false, merged};
}

void insert(int x, int idx, int a, int b){
  if(a + 1 == b){
    if(a != x)
      return;
    if(segtree[idx].factors.size() == 0)
      segtree[idx].factors = primefactors[x + 1];
    else
      segtree[idx].factors = vector<int>();
    return;
  }
  if(x < a || x >= b)
    return;
  int center = (a + b) / 2;
  int l = idx * 2;
  int r = idx * 2 + 1;
  insert(x, l, a, center);
  insert(x, r, center, b);
  segtree[idx] = merge(segtree[l], segtree[r]);
}


node query(int l, int r, int idx, int a, int b){
  if(l >= b || r <= a)
    return node{false, vector<int>()};
  vector<int> merged;
  if(l <= a && r >= b){
    return segtree[idx];
  }
  int center = (a + b) / 2;
  node left = query(l, r, idx * 2, a, center);
  node right = query(l, r, idx * 2 + 1, center, b);
  return merge(left, right);
}


int main(int, char**){
  int n, q;
  cin >> n >> q;
  for (int i = 2; i < n + 1; i++)
  {
    if(primefactors[i].size() == 0){
      for(int j = i; j < n + 1; j += i){
        primefactors[j].push_back(i);
      }
    }
  }
  for (int i = 0; i < q; i++)
  {
    char qy;
    cin >> qy;
    if(qy == 'S'){
      int x;
      cin >> x;
      insert(x - 1, 1, 0, n);
    } else if(qy == 'C'){
      int l, r;
      cin >> l >> r;
      cout << (query(l - 1, r, 1, 0, n).collision ? "DA\n" : "NE\n");
    }
  }
}

Compilation message

Main.cpp: In function 'node merge(node, node)':
Main.cpp:25:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   while(i < a.factors.size() || j < b.factors.size()){
      |         ~~^~~~~~~~~~~~~~~~~~
Main.cpp:25:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   while(i < a.factors.size() || j < b.factors.size()){
      |                                 ~~^~~~~~~~~~~~~~~~~~
Main.cpp:26:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(i == a.factors.size()){
      |        ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:31:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if(i == b.factors.size()){
      |        ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 149072 KB Output is correct
2 Correct 29 ms 149072 KB Output is correct
3 Correct 37 ms 149148 KB Output is correct
4 Correct 31 ms 148964 KB Output is correct
5 Correct 33 ms 149080 KB Output is correct
6 Correct 29 ms 149152 KB Output is correct
7 Correct 30 ms 149076 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 309452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 149072 KB Output is correct
2 Correct 29 ms 149072 KB Output is correct
3 Correct 37 ms 149148 KB Output is correct
4 Correct 31 ms 148964 KB Output is correct
5 Correct 33 ms 149080 KB Output is correct
6 Correct 29 ms 149152 KB Output is correct
7 Correct 30 ms 149076 KB Output is correct
8 Runtime error 177 ms 309452 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -