Submission #53068439

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

vector<int> min_fac, num, A;
vector<vector<pair<int, int>>> new_factor;
vector<vector<int>> factor;
int N, Q, danger = 0;

void add(int i) {
    for(auto kv : new_factor[i]) {
        int k = kv.first, v = kv.second;
        num[k] += v;
        if(num[k] % 3 != 0 && (num[k] - v) % 3 == 0)
            danger++;
        if(num[k] % 3 == 0 && (num[k] - v) % 3 != 0)
            danger--;
    }
}

void del(int i) {
    for(auto kv : new_factor[i]) {
        int k = kv.first, v = kv.second;
        num[k] -= v;
        if(num[k] % 3 == 0 && (num[k] + v) % 3 != 0)
            danger--;
        if(num[k] % 3 != 0 && (num[k] + v) % 3 == 0)
            danger++;
    }
}

void Eratosthenes() {
    int n = *max_element(A.begin(), A.end());
    vector<bool> primes(n + 1, true);
    primes[0] = primes[1] = false;

    for(int i = 2; i <= n; i++) {
        if(primes[i]) {
            min_fac[i] = i;
            for(int j = 2 * i; j <= n; j += i) {
                primes[j] = false;
                if(min_fac[j] == -1)
                    min_fac[j] = i;
            }
        }
    }
}

void Factorization() {
    for(int i = 0; i < N; i++) {
        int now = A[i];
        while(true) {
            if(now == 1)
                break;
            if(min_fac[now] == now) {
                factor[i].push_back(now);
                break;
            } else {
                factor[i].push_back(min_fac[now]);
                now /= min_fac[now];
            }
        }
    }
}

int main() {
    cin >> N >> Q;
    int block = int(N / pow(Q, 0.5)) + 1;
    vector<vector<pair<int, pair<int, int>>>> queries((int)(pow(Q, 0.5)+1));

    A.resize(N);
    for(int i = 0; i < N; i++)
        cin >> A[i];

    for(int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R;
        L--; R--; // 0-indexed
        queries[L / block].push_back(make_pair(i, make_pair(L, R)));
    }

    min_fac = vector<int>(*max_element(A.begin(), A.end()) + 1, -1);
    factor = vector<vector<int>>(N);
    Eratosthenes();
    Factorization();

    new_factor.resize(N);
    for(int i = 0; i < N; i++) {
        map<int, int> d;
        for(int j : factor[i])
            d[j]++;
        for(auto kv : d)
            new_factor[i].push_back(kv);
    }

    vector<int> ans(Q);
    int left = 0, right = 0;
    num = vector<int>(*max_element(A.begin(), A.end()) + 1, 0);
    danger = 0;

    for(int ind = 0; ind < queries.size(); ind++) {
        sort(queries[ind].begin(), queries[ind].end(), [&](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
            if(ind % 2 == 0)
                return a.second.second < b.second.second;
            else
                return a.second.second > b.second.second;
        });
        for(auto query : queries[ind]) {
            int i = query.first, l = query.second.first, r = query.second.second;
            while(right <= r) {
                add(right);
                right++;
            }
            while(l < left) {
                left--;
                add(left);
            }
            while(r + 1 < right) {
                right--;
                del(right);
            }
            while(left < l) {
                del(left);
                left++;
            }
            ans[i] = (danger == 0);
        }
    }

    for(int res : ans)
        cout << (res ? "Yes" : "No") << endl;

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:100:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<std::pair<int, std::pair<int, int> > > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  100 |     for(int ind = 0; ind < queries.size(); ind++) {
      |                      ~~~~^~~~~~~~~~~~~~~~

Judge Result