oj.uz

Submission #1069042

# Submission time Handle Problem Language Result Execution time Memory
1069042 2024-08-21T15:11:32 Z Andrey Diversity (CEOI21_diversity) C++14
4 / 100
 7000 ms 91224 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 = 2;

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 3 ms 13404 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13520 KB Output is correct
5 Correct 4 ms 13404 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 3 ms 13404 KB Output is correct
8 Correct 3 ms 13468 KB Output is correct
9 Correct 3 ms 13404 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 13548 KB Output is correct
2 Correct 50 ms 13400 KB Output is correct
3 Correct 505 ms 21760 KB Output is correct
4 Execution timed out 7041 ms 91224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13548 KB Output is correct
2 Correct 50 ms 13400 KB Output is correct
3 Correct 505 ms 21760 KB Output is correct
4 Execution timed out 7041 ms 91224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13548 KB Output is correct
2 Correct 50 ms 13400 KB Output is correct
3 Correct 505 ms 21760 KB Output is correct
4 Execution timed out 7041 ms 91224 KB Time limit exceeded
5 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 3 ms 13404 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13520 KB Output is correct
5 Correct 4 ms 13404 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 3 ms 13404 KB Output is correct
8 Correct 3 ms 13468 KB Output is correct
9 Correct 3 ms 13404 KB Output is correct
10 Correct 4 ms 13404 KB Output is correct
11 Correct 8 ms 13548 KB Output is correct
12 Correct 50 ms 13400 KB Output is correct
13 Correct 505 ms 21760 KB Output is correct
14 Execution timed out 7041 ms 91224 KB Time limit exceeded
15 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 3 ms 13404 KB Output is correct
3 Correct 3 ms 13404 KB Output is correct
4 Correct 3 ms 13520 KB Output is correct
5 Correct 4 ms 13404 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 3 ms 13404 KB Output is correct
8 Correct 3 ms 13468 KB Output is correct
9 Correct 3 ms 13404 KB Output is correct
10 Correct 4 ms 13404 KB Output is correct
11 Correct 8 ms 13548 KB Output is correct
12 Correct 50 ms 13400 KB Output is correct
13 Correct 505 ms 21760 KB Output is correct
14 Execution timed out 7041 ms 91224 KB Time limit exceeded
15 Halted 0 ms 0 KB -