Submission #1069052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069052		Andrey	Diversity (CEOI21_diversity)	C++14	100 / 100	6167 ms	254804 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;
        }
        if(bruh[i].size() > 0) {
            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:41:36: 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]
   41 |             for(long long j = 0; j < br.size(); j++) {
      |                                  ~~^~~~~~~~~~~
diversity.cpp:46:36: 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]
   46 |             for(long long j = 0; j < bruh[i].size(); j++) {
      |                                  ~~^~~~~~~~~~~~~~~~
diversity.cpp:90:25: 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]
   90 |                 while(y < bruh[i].size() && bruh[i][y].first.first == j) {
      |                       ~~^~~~~~~~~~~~~~~~
diversity.cpp:144:44: 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]
  144 |                     for(long long z = 0; z < wut.size(); z++) {
      |                                          ~~^~~~~~~~~~~~
diversity.cpp:148:44: 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]
  148 |                     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: 26 / 26
• Subtask 6: 36 / 36