oj.uz

Submission #531364

# Submission time Handle Problem Language Result Execution time Memory
531364 2022-02-28T14:09:30 Z azberjibiou Diversity (CEOI21_diversity) C++17
4 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=300003;
const int mxM=1010;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1e18;
const ll P1=1000000007;
const ll P2=1000000009;
typedef struct query{
    int s, e, idx;
    ll ans;
}query;
int N, M, Q, L;
int A[mxN];
query T[mxN];
int ncnt[mxN];  ///number
int tcnt[mxN];  ///type
int typ_cnt;
int ns=1, ne;
unordered_map <int, int> s;
ll ans;
ll lval, rval;
int nsum;
bool cmp1(query a, query b)
{
    if(a.s/M!=b.s/M)    return a.s<b.s;
    return a.e<b.e;
}
void set_remove(int now)
{
    if(now<=M)  tcnt[now]--;
    else
    {
        s[now]--;
        if(s[now]==0)   s.erase(now);
    }
}
void set_insert(int now)
{
    if(now<=M)  tcnt[now]++;
    else    s[now]++;
}
void mo(int pos, int typ)
{
    int pre=ncnt[A[pos]], now=ncnt[A[pos]]+typ;
    ncnt[A[pos]]+=typ;
    if(pre==0)  typ_cnt++;
    if(now==0)  typ_cnt--;
    set_remove(pre);
    set_insert(now);
}
ll sum(ll a, ll d, ll n)
{
    return (a*(a+1)*n+(2*a+1)*d*n*(n-1)/2+d*d*(n-1)*n*(2*n-1)/6)/2;
}
void typ_insert(int now, int num)
{
    if(num==0)  return;
    nsum+=num;
    if(nsum==typ_cnt) num--;
    if(num==0)  return;
    if(lval>rval)   swap(lval, rval);
    int lcnt=0, rcnt=0;
    lcnt+=min((ll)num, (rval-lval)/now);
    num-=lcnt;
    if(num%2==0)    lcnt+=num/2, rcnt+=num/2;
    else    lcnt+=num/2+1, rcnt+=num/2;
    ans-=sum(lval+now, now, lcnt);
    ans-=sum(L-lval-lcnt*now, now, lcnt);
    lval+=lcnt*now;
    ans-=sum(rval+now, now, rcnt);
    ans-=sum(L-rval-rcnt*now, now, rcnt);
    rval+=rcnt*now;
}
void print()
{
    for(int i=1;i<=M;i++)   printf("cnt[%d]=%d\n", i, tcnt[i]);
    for(auto iter=s.begin();iter!=s.end();iter++)   printf("%d ", *iter);
    printf("\n");
}
int main()
{
    gibon
    cin >> N >> Q;
    M=sqrt(N);
    for(int i=1;i<=N;i++)   cin >> A[i];
    for(int i=0;i<Q;i++)
    {
        cin >> T[i].s >> T[i].e;
        T[i].idx=i;
    }
    sort(T, T+Q, cmp1);
    for(int i=0;i<Q;i++)
    {
        while(ne<T[i].e)
        {
            ne++;
            mo(ne, 1);
        }
        while(ns>T[i].s)
        {
            ns--;
            mo(ns, 1);
        }
        while(ne>T[i].e)
        {
            mo(ne, -1);
            ne--;
        }
        while(ns<T[i].s)
        {
            mo(ns, -1);
            ns++;
        }
        L=T[i].e-T[i].s+1;
        nsum=0;
        ans=(ll)L*(L+1)/2*typ_cnt;
        lval=0, rval=0;
        for(int i=1;i<=M;i++)
        {
            typ_insert(i, tcnt[i]);
        }
        for(auto ele : s)
        {
            typ_insert(ele.fir, ele.sec);
        }
        T[i].ans=ans;
    }
    sort(T, T+Q, [](query a, query b){return a.idx<b.idx;});
    for(int i=0;i<Q;i++)    cout << T[i].ans << '\n';
}

Compilation message

diversity.cpp: In function 'void print()':
diversity.cpp:91:62: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::pair<const int, int>' [-Wformat=]
   91 |     for(auto iter=s.begin();iter!=s.end();iter++)   printf("%d ", *iter);
      |                                                             ~^    ~~~~~
      |                                                              |    |
      |                                                              int  std::pair<const int, int>

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -