Submission #1003696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003696		thelepi	Radio (COCI22_radio)	C++17	110 / 110	927 ms	199504 KiB

Main

#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[1000010];

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(j == b.factors.size()){
      merged.push_back(a.factors[i]);
      i++;
      continue;
    }
    if(a.factors[i] == b.factors[j]){
      return node{true, vector<int>()};
    }
    assert((i < a.factors.size()));
    assert((j < b.factors.size()));
    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 (stderr)

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(j == b.factors.size()){
      |        ~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from Main.cpp:3:
Main.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     assert((i < a.factors.size()));
      |             ~~^~~~~~~~~~~~~~~~~~
Main.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     assert((j < b.factors.size()));
      |             ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70