oj.uz

Submission #792204

# Submission time Handle Problem Language Result Execution time Memory
792204 2023-07-24T17:30:59 Z cig32 Radio (COCI22_radio) C++17
110 / 110
 1137 ms 312372 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
//#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int spf[MAXN];
vector<int> List[MAXN];
multiset<int> base[MAXN];
set<int> all[MAXN];
int seg[2*MAXN];

int n;
void update(int i, int v) {
  i--;
  seg[i += n] = v;
  while(i /= 2) seg[i] = min(seg[2*i], seg[2*i+1]);
}
int query_min(int l, int r) {
  l--, r--;
  int ans = 2e6;
  for (l += n, r += n; l <= r; ++l/=2, --r/=2) {
		if (l%2 == 1) ans = min(ans, seg[l]);
		if (r%2 == 0) ans = min(ans, seg[r]);
	}
	return ans;
}
	
void insert_segment(int l, int r) {
  base[l].insert(r);
  update(l, *base[l].begin());
}

void delete_segment(int l, int r) {
  auto it = base[l].lower_bound(r);
  base[l].erase(it);
  update(l, *base[l].begin());
}

bool query_segment(int l, int r) {
  return query_min(l, r) <= r;
}

void solve(int tc) {
  for(int i=0; i<2*MAXN; i++) seg[i] = 2e6;
  for(int i=2; i*i<MAXN; i++) {
    if(spf[i] == 0) {
      spf[i] = i;
      for(int j=i*i; j<MAXN; j+=i) {
        spf[j] = (spf[j] ? spf[j] : i);
      }
    }
  }
  for(int i=2; i<MAXN; i++) {
    if(spf[i] == 0) spf[i] = i;
  }
  int q;
  cin >> n >> q;
  bool stat[n+1];
  for(int i=1; i<=n; i++) stat[i] = 0;
  for(int i=1; i<=n; i++) {
    update(i, 2e6);
  }
  for(int i=1; i<=n; i++) {
    all[i].insert(2e6);
    all[i].insert(0);
    base[i].insert(2e6);
  }
  while(q--) {
    char t;
    cin >> t;
    if(t == 'S') {
      int x;
      cin >> x;
      vector<int> List;
      int z = x;
      while(z > 1) {
        if(spf[z / spf[z]] != spf[z]) List.push_back(spf[z]);
        z /= spf[z];
      }
      if(stat[x] == 0) {
        stat[x] = 1;
        for(int i=0; i<List.size(); i++) {
          int y = List[i];
          auto it_fro = all[y].lower_bound(x);
          int fro = *it_fro;
          if(fro != 2e6) insert_segment(x, fro);
          it_fro--;
          int uwu = *it_fro;
          if(uwu != 0) insert_segment(uwu, x);
          if(uwu != 0 && fro != 2e6) delete_segment(uwu, fro);
          all[y].insert(x);
        }
      }
      else {
        stat[x] = 0;
        for(int i=0; i<List.size(); i++) {
          int y = List[i];
          all[y].erase(x);
          auto it_fro = all[y].lower_bound(x);
          int fro = *it_fro;
          if(fro != 2e6) delete_segment(x, fro);
          it_fro--;
          int uwu = *it_fro;
          if(uwu != 0) delete_segment(uwu, x);
          if(uwu != 0 && fro != 2e6) insert_segment(uwu, fro);
        }
      }
    }
    else {
      int l, r;
      cin >> l >> r;
      cout << (query_segment(l, r) ? "DA\n" : "NE\n");
    }
  }
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

Main.cpp: In function 'void solve(int)':
Main.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int i=0; i<List.size(); i++) {
      |                      ~^~~~~~~~~~~~
Main.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i=0; i<List.size(); i++) {
      |                      ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 129356 KB Output is correct
2 Correct 63 ms 129400 KB Output is correct
3 Correct 72 ms 129396 KB Output is correct
4 Correct 59 ms 129460 KB Output is correct
5 Correct 59 ms 129488 KB Output is correct
6 Correct 61 ms 129432 KB Output is correct
7 Correct 60 ms 129360 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 155568 KB Output is correct
2 Correct 782 ms 230280 KB Output is correct
3 Correct 994 ms 307248 KB Output is correct
4 Correct 84 ms 143776 KB Output is correct
5 Correct 176 ms 201184 KB Output is correct
6 Correct 300 ms 272860 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 129356 KB Output is correct
2 Correct 63 ms 129400 KB Output is correct
3 Correct 72 ms 129396 KB Output is correct
4 Correct 59 ms 129460 KB Output is correct
5 Correct 59 ms 129488 KB Output is correct
6 Correct 61 ms 129432 KB Output is correct
7 Correct 60 ms 129360 KB Output is correct
8 Correct 376 ms 155568 KB Output is correct
9 Correct 782 ms 230280 KB Output is correct
10 Correct 994 ms 307248 KB Output is correct
11 Correct 84 ms 143776 KB Output is correct
12 Correct 176 ms 201184 KB Output is correct
13 Correct 300 ms 272860 KB Output is correct
14 Correct 217 ms 131272 KB Output is correct
15 Correct 401 ms 144148 KB Output is correct
16 Correct 1137 ms 312372 KB Output is correct
17 Correct 922 ms 305100 KB Output is correct
18 Correct 1072 ms 308852 KB Output is correct
19 Correct 1044 ms 308856 KB Output is correct
20 Correct 310 ms 272768 KB Output is correct
21 Correct 332 ms 272824 KB Output is correct
22 Correct 300 ms 272768 KB Output is correct
23 Correct 312 ms 272920 KB Output is correct