Submission #26267842

---

Source Code Expand

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

constexpr int logn = 20; 

ll triangleorder(int l,int r) {
    ll d = 0;
    for (ll s = 1<<logn-1; s > 1; s>>=1) {
        if (l >= s) {
            d += (36*s*s)>>4;
            l -= s;
            r -= s;
        }
        else if (l+r > s<<1) {
            d += (24*s*s)>>4;
            l = l+1;
            r = (s<<1)-r;
            swap(l,r);
        }
        else if (r > s) {
            d += (12*s*s)>>4;
            l = s-l;
            r = r-s-1;
            swap(l,r);
        }
    }
    d += l+r-1;
    return d;
}

int main() {
    int n,q;cin >> n >> q;
    vector<int> c(n),l(q),r(q),idx(q),cnt(n,0),ans(q);
    vector<ll> ord(q);
    int count = 0, now_l = 0, now_r = 0;
    for (int i = 0; i < n; i++) { scanf("%d",&c[i]); c[i]--; }
    for (int i = 0; i < q; i++) { scanf("%d %d",&l[i], &r[i]); l[i]--; }
    for (int i = 0; i < q; i++) { ord[i] = triangleorder(l[i],r[i]); }
    iota(idx.begin(), idx.end(),0);
    sort(idx.begin(), idx.end(), [&](int a,int b) { return ord[a] < ord[b]; });
    auto add = [&](int x) {
        if (cnt[c[x]] == 0) count++;
        cnt[c[x]]++;
    };
    auto del = [&](int x) {
        cnt[c[x]]--;
        if (cnt[c[x]] == 0) count--;
    };
    for (int i = 0; i < q; i++) {
        while(now_l > l[idx[i]]) add(--now_l);
        while(now_r < r[idx[i]]) add(now_r++);
        while(now_l < l[idx[i]]) del(now_l++);
        while(now_r > r[idx[i]]) del(--now_r);
        ans[idx[i]] = count;
    }
    for (int i = 0; i < q; i++) printf("%d\n",ans[i]);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll triangleorder(int, int)’:
./Main.cpp:9:24: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
    9 |     for (ll s = 1<<logn-1; s > 1; s>>=1) {
      |                    ~~~~^~
./Main.cpp: In function ‘int main()’:
./Main.cpp:37:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   37 |     for (int i = 0; i < n; i++) { scanf("%d",&c[i]); c[i]--; }
      |                                   ~~~~~^~~~~~~~~~~~
./Main.cpp:38:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   38 |     for (int i = 0; i < q; i++) { scanf("%d %d",&l[i], &r[i]); l[i]--; }
      |                                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Judge Result