Submission #1069047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069047		Andrey	Diversity (CEOI21_diversity)	C++14	38 / 100	7045 ms	251252 KiB

diversity

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

long long pr[300001][101];
vector<long long> haha(300001);
vector<long long> br(300001);
vector<pair<pair<long long,long long>,long long>> bruh[300001];
const long long k = 100;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,l,r;
    cin >> n >> q;
    for(long long i = 1; i <= 100; i++) {
        for(long long j = 0; j <= n; j++) {
            pr[j][i] = j*(j+1)/2;
            if(j >= i) {
                pr[j][i]+=pr[j-i][i];
            }
        }
    }
    for(long long i = 1; i <= n; i++) {
        cin >> haha[i];
    }
    for(long long i = 0; i < q; i++) {
        cin >> l >> r;
        bruh[l/k].push_back({{r,l},i});
    }
    vector<long long> ans(q);
    for(long long i = 0; i < n; i++) {
        sort(bruh[i].begin(),bruh[i].end());
    }
    for(long long i = 0; i < n; i++) {
        if(i*k > n) {
            break;
        }
        for(long long j = 0; j < br.size(); j++) {
            br[j] = 0;
        }
        long long y = bruh[i].size();
        vector<long long> wow(k+1);
        for(long long j = 0; j < bruh[i].size(); j++) {
            if(bruh[i][j].first.first >= (i+1)*k) {
                y = j;
                break;
            }
            r = bruh[i][j].first.first,l = bruh[i][j].first.second;
            for(long long j = l; j <= r; j++) {
                wow[br[haha[j]]]--;
                br[haha[j]]++;
                wow[br[haha[j]]]++;
            }
            long long pl = 0,pr = 0,sb = 0;
            for(long long j = 1; j <= k; j++) {
                for(long long x = 0; x < wow[j]; x++) {
                    if(pl > pr) {
                        swap(pr,pl);
                    }
                    long long m = r-l+1;
                    sb+=m*(m+1)/2;
                    sb-=pl*(pl+1)/2;
                    long long c = m-pl-j;
                    sb-=c*(c+1)/2;
                    pl+=j;
                }
            }
            ans[bruh[i][j].second] = sb;
            for(long long j = l; j <= r; j++) {
                br[haha[j]] = 0;
            }
            for(long long j = 0; j <= k; j++) {
                wow[j] = 0;
            }
        }
        vector<long long> wut(0);
        for(long long j = (i+1)*k; j <= n; j++) {
            if(br[haha[j]] < k) {
                wow[br[haha[j]]]--;
                wow[br[haha[j]]+1]++;
            }
            else if(br[haha[j]] == k) {
                wow[br[haha[j]]]--;
                wut.push_back(haha[j]);
            }
            br[haha[j]]++;
            while(y < bruh[i].size() && bruh[i][y].first.first == j) {
                vector<long long> troll(k+1);
                for(long long z = 0; z <= k; z++) {
                    troll[z] = wow[z];
                }
                r = bruh[i][y].first.first,l = bruh[i][y].first.second;
                for(long long z = l; z < (i+1)*k; z++) {
                    if(br[haha[z]] < k) {
                        wow[br[haha[z]]]--;
                        wow[br[haha[z]]+1]++;
                    }
                    else if(br[haha[z]] == k) {
                        wow[br[haha[z]]]--;
                        wut.push_back(haha[z]);
                    }
                    br[haha[z]]++;
                }
                long long ql = 0,qr = 0,sb = 0,m = (r-l+1);
                for(long long j = 1; j <= k; j++) {
                    long long a = wow[j];
                    if(ql > qr) {
                        swap(ql,qr);
                    }
                    sb+=(m*(m+1)/2)*a;
                    long long d = (a+1)/2;
                    if(d > 0) {
                        sb-=pr[ql+j*(d-1)][j];
                        if(ql >= j) {
                            sb+=pr[ql-j][j];
                        }
                        long long c = m-ql-j;
                        sb-=pr[c][j];
                        if(c >= d*j) {
                            sb+=pr[c-d*j][j];
                        }
                    }
                    d = a/2;
                    swap(ql,qr);
                    if(d > 0) {
                        sb-=pr[ql+j*(d-1)][j];
                        if(ql >= j) {
                            sb+=pr[ql-j][j];
                        }
                        long long c = m-ql-j;
                        sb-=pr[c][j];
                        if(c >= d*j) {
                            sb+=pr[c-d*j][j];
                        }
                    }
                    swap(ql,qr);
                    ql+=j*((a+1)/2);
                    qr+=j*(a/2);
                }
                vector<long long> banana(0);
                for(long long z = 0; z < wut.size(); z++) {
                    banana.push_back(br[wut[z]]);
                }
                sort(banana.begin(),banana.end());
                for(long long z = 0; z < banana.size(); z++) {
                    long long a = banana[z];
                    if(ql > qr) {
                        swap(ql,qr);
                    }
                    sb+=m*(m+1)/2;
                    sb-=ql*(ql+1)/2;
                    long long c = m-ql-a;
                    sb-=c*(c+1)/2;
                    ql+=a;
                }
                ans[bruh[i][y].second] = sb;
                for(long long z = l; z < (i+1)*k; z++) {
                    br[haha[z]]--;
                }
                while(!wut.empty() && br[wut[wut.size()-1]] <= k) {
                    wut.pop_back();
                }
                for(long long z = 0; z <= k; z++) {
                    wow[z] = troll[z];
                }
                y++;
            }
        }
    }
    for(long long i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:40:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(long long j = 0; j < br.size(); j++) {
      |                              ~~^~~~~~~~~~~
diversity.cpp:45:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(long long j = 0; j < bruh[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
diversity.cpp:89:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             while(y < bruh[i].size() && bruh[i][y].first.first == j) {
      |                   ~~^~~~~~~~~~~~~~~~
diversity.cpp:143:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 for(long long z = 0; z < wut.size(); z++) {
      |                                      ~~^~~~~~~~~~~~
diversity.cpp:147:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |                 for(long long z = 0; z < banana.size(); z++) {
      |                                      ~~^~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36