oj.uz

Submission #1069043

# Submission time Handle Problem Language Result Execution time Memory
1069043 2024-08-21T15:12:27 Z Andrey Diversity (CEOI21_diversity) C++14
4 / 100
 7000 ms 170580 KB 
#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++) {
        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

diversity.cpp: In function 'int main()':
diversity.cpp:37: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]
   37 |         for(long long j = 0; j < br.size(); j++) {
      |                              ~~^~~~~~~~~~~
diversity.cpp:42: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]
   42 |         for(long long j = 0; j < bruh[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
diversity.cpp:86: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]
   86 |             while(y < bruh[i].size() && bruh[i][y].first.first == j) {
      |                   ~~^~~~~~~~~~~~~~~~
diversity.cpp:140: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]
  140 |                 for(long long z = 0; z < wut.size(); z++) {
      |                                      ~~^~~~~~~~~~~~
diversity.cpp:144: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]
  144 |                 for(long long z = 0; z < banana.size(); z++) {
      |                                      ~~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13404 KB Output is correct
2 Correct 4 ms 13400 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13404 KB Output is correct
5 Correct 3 ms 13504 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 4 ms 13404 KB Output is correct
8 Correct 4 ms 13400 KB Output is correct
9 Correct 4 ms 13540 KB Output is correct
10 Correct 4 ms 13404 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13404 KB Output is correct
2 Correct 50 ms 13456 KB Output is correct
3 Correct 484 ms 21592 KB Output is correct
4 Correct 5086 ms 91228 KB Output is correct
5 Execution timed out 7068 ms 170580 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13404 KB Output is correct
2 Correct 50 ms 13456 KB Output is correct
3 Correct 484 ms 21592 KB Output is correct
4 Correct 5086 ms 91228 KB Output is correct
5 Execution timed out 7068 ms 170580 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13404 KB Output is correct
2 Correct 50 ms 13456 KB Output is correct
3 Correct 484 ms 21592 KB Output is correct
4 Correct 5086 ms 91228 KB Output is correct
5 Execution timed out 7068 ms 170580 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13404 KB Output is correct
2 Correct 4 ms 13400 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13404 KB Output is correct
5 Correct 3 ms 13504 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 4 ms 13404 KB Output is correct
8 Correct 4 ms 13400 KB Output is correct
9 Correct 4 ms 13540 KB Output is correct
10 Correct 4 ms 13404 KB Output is correct
11 Correct 8 ms 13404 KB Output is correct
12 Correct 50 ms 13456 KB Output is correct
13 Correct 484 ms 21592 KB Output is correct
14 Correct 5086 ms 91228 KB Output is correct
15 Execution timed out 7068 ms 170580 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13404 KB Output is correct
2 Correct 4 ms 13400 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13404 KB Output is correct
5 Correct 3 ms 13504 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 4 ms 13404 KB Output is correct
8 Correct 4 ms 13400 KB Output is correct
9 Correct 4 ms 13540 KB Output is correct
10 Correct 4 ms 13404 KB Output is correct
11 Correct 8 ms 13404 KB Output is correct
12 Correct 50 ms 13456 KB Output is correct
13 Correct 484 ms 21592 KB Output is correct
14 Correct 5086 ms 91228 KB Output is correct
15 Execution timed out 7068 ms 170580 KB Time limit exceeded
16 Halted 0 ms 0 KB -