oj.uz

Submission #576931

# Submission time Handle Problem Language Result Execution time Memory
576931 2022-06-13T20:36:35 Z MilosMilutinovic Radio (COCI22_radio) C++14
110 / 110
 1439 ms 246228 KB 
/**
 *    author:  wxhtzdy
 *    created: 13.06.2022 22:14:19
**/
#include <bits/stdc++.h>

using namespace std;
        
const int MAX = 1000005;

const int inf = (int) 1e9;

int mn[8 * MAX];

void build(int node, int l, int r) {
  mn[node] = inf;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  build(node * 2, l, mid);
  build(node * 2 + 1, mid + 1, r);
}

void modify(int node, int l, int r, int i, int v) {
  if (l == r) {
    mn[node] = v;
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    modify(node * 2, l, mid, i, v);
  } else {
    modify(node * 2 + 1, mid + 1, r, i, v);
  }
  mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
}

int get(int node, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll) {
    return inf;
  }
  if (ll <= l && r <= rr) {
    return mn[node];
  }
  int mid = l + r >> 1;
  return min(get(node * 2, l, mid, ll, rr), get(node * 2 + 1, mid + 1, r, ll, rr));
} 

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  vector<vector<int>> d(MAX);
  for (int i = 2; i < MAX; i++) {
    if (d[i].empty()) {
      for (int j = i; j < MAX; j += i) {
        d[j].push_back(i);
      }
    }
  }                    
  build(1, 1, MAX);
  vector<multiset<int>> f(MAX);
  for (int i = 0; i < MAX; i++) {
    f[i].insert(inf);
  }
  function<void(int, int)> Add_seg = [&](int l, int r) {
    f[l].insert(r);
    modify(1, 1, MAX, l, *f[l].begin());
  };
  function<void(int, int)> Del_seg = [&](int l, int r) {
    assert(f[l].find(r) != f[l].end());
    f[l].erase(f[l].find(r));
    modify(1, 1, MAX, l, *f[l].begin());
  };
  vector<multiset<int>> at(MAX);
  function<void(int)> Del = [&](int x) {
    for (int i : d[x]) {
      auto it = at[i].find(x);
      if (it != at[i].begin()) {
        Del_seg(*prev(it), x);   
      }
      if (it != prev(at[i].end())) {
        Del_seg(x, *next(it));
      }
      if (it != at[i].begin() && it != prev(at[i].end())) {
        Add_seg(*prev(it), *next(it));
      }
      at[i].erase(it);
    }
  };
  function<void(int)> Add = [&](int x) {
    for (int i : d[x]) {
      auto it = at[i].lower_bound(x);
      if (it != at[i].begin() && it != at[i].end()) {
        Del_seg(*prev(it), *it);
      }
      if (it != at[i].begin()) {
        Add_seg(*prev(it), x);
      }             
      if (it != at[i].end()) {
        Add_seg(x, *it);
      }
      at[i].insert(x);
    }
  };
  int n, q;
  cin >> n >> q;
  vector<bool> act(MAX);
  while (q--) {
    char foo;
    cin >> foo;
    if (foo == 'S') {
      int x;
      cin >> x;
      if (act[x]) {
        Del(x);
      } else {
        Add(x);
      }
      act[x] = !act[x];
    } else {
      int l, r;
      cin >> l >> r;
      cout << (get(1, 1, MAX, l, r) <= r ? "DA" : "NE") << '\n';
    }
  }                                                                      
  return 0;
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:20:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void modify(int, int, int, int, int)':
Main.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int get(int, int, int, int, int)':
Main.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 204944 KB Output is correct
2 Correct 423 ms 205028 KB Output is correct
3 Correct 406 ms 205128 KB Output is correct
4 Correct 421 ms 204960 KB Output is correct
5 Correct 415 ms 204972 KB Output is correct
6 Correct 436 ms 204980 KB Output is correct
7 Correct 423 ms 205048 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 890 ms 217008 KB Output is correct
2 Correct 1242 ms 234852 KB Output is correct
3 Correct 1302 ms 240988 KB Output is correct
4 Correct 413 ms 205124 KB Output is correct
5 Correct 423 ms 205724 KB Output is correct
6 Correct 452 ms 206528 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 204944 KB Output is correct
2 Correct 423 ms 205028 KB Output is correct
3 Correct 406 ms 205128 KB Output is correct
4 Correct 421 ms 204960 KB Output is correct
5 Correct 415 ms 204972 KB Output is correct
6 Correct 436 ms 204980 KB Output is correct
7 Correct 423 ms 205048 KB Output is correct
8 Correct 890 ms 217008 KB Output is correct
9 Correct 1242 ms 234852 KB Output is correct
10 Correct 1302 ms 240988 KB Output is correct
11 Correct 413 ms 205124 KB Output is correct
12 Correct 423 ms 205724 KB Output is correct
13 Correct 452 ms 206528 KB Output is correct
14 Correct 691 ms 206636 KB Output is correct
15 Correct 1012 ms 212836 KB Output is correct
16 Correct 1439 ms 246228 KB Output is correct
17 Correct 1234 ms 238952 KB Output is correct
18 Correct 1322 ms 242748 KB Output is correct
19 Correct 1318 ms 242520 KB Output is correct
20 Correct 460 ms 206480 KB Output is correct
21 Correct 469 ms 206600 KB Output is correct
22 Correct 456 ms 206620 KB Output is correct
23 Correct 450 ms 206540 KB Output is correct