oj.uz

Submission #1003696

# Submission time Handle Problem Language Result Execution time Memory
1003696 2024-06-20T15:43:15 Z thelepi Radio (COCI22_radio) C++17
110 / 110
 927 ms 199504 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[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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 148944 KB Output is correct
2 Correct 51 ms 149072 KB Output is correct
3 Correct 54 ms 149116 KB Output is correct
4 Correct 55 ms 149072 KB Output is correct
5 Correct 55 ms 149076 KB Output is correct
6 Correct 55 ms 149148 KB Output is correct
7 Correct 56 ms 149072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 156496 KB Output is correct
2 Correct 336 ms 176980 KB Output is correct
3 Correct 539 ms 197712 KB Output is correct
4 Correct 88 ms 152400 KB Output is correct
5 Correct 325 ms 165852 KB Output is correct
6 Correct 716 ms 182868 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 148944 KB Output is correct
2 Correct 51 ms 149072 KB Output is correct
3 Correct 54 ms 149116 KB Output is correct
4 Correct 55 ms 149072 KB Output is correct
5 Correct 55 ms 149076 KB Output is correct
6 Correct 55 ms 149148 KB Output is correct
7 Correct 56 ms 149072 KB Output is correct
8 Correct 186 ms 156496 KB Output is correct
9 Correct 336 ms 176980 KB Output is correct
10 Correct 539 ms 197712 KB Output is correct
11 Correct 88 ms 152400 KB Output is correct
12 Correct 325 ms 165852 KB Output is correct
13 Correct 716 ms 182868 KB Output is correct
14 Correct 207 ms 150612 KB Output is correct
15 Correct 256 ms 153944 KB Output is correct
16 Correct 573 ms 199504 KB Output is correct
17 Correct 609 ms 197520 KB Output is correct
18 Correct 650 ms 198484 KB Output is correct
19 Correct 617 ms 198480 KB Output is correct
20 Correct 707 ms 182732 KB Output is correct
21 Correct 855 ms 183120 KB Output is correct
22 Correct 927 ms 183124 KB Output is correct
23 Correct 877 ms 183380 KB Output is correct