oj.uz

Submission #697830

# Submission time Handle Problem Language Result Execution time Memory
697830 2023-02-11T07:10:55 Z azberjibiou Swap Swap Sort (CCO21_day1problem1) C++17
8 / 25
 2632 ms 96580 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int mxN=100005;
ll N, M, K, Q;
int A[mxN];
ll cnt[mxN];
int B[mxN];
vector <int> v[mxN];
vector <int> big;
vector <ll> pref[mxN];
map <pii, ll> mp;  ///mp[a, b] = a ... b 의 개수
ll ans;
void make_bb()
{
    for(int i=0;i<big.size();i++)
    {
        for(int j=i+1;j<big.size();j++)
        {
            int n1=big[i], n2=big[j];
            ll inv=0;
            int idx=0;
            for(int k=0;k<v[n2].size();k++)
            {
                while(idx!=v[n1].size() && v[n1][idx]<v[n2][k]) idx++;
                inv+=idx;
            }
            mp[pii(n1, n2)]=inv;
        }
    }
}
void make_pref()
{
    for(int now : big)
    {
        pref[now].resize(N+1);
        pref[now][0]=0;
        for(int i=1;i<=N;i++)   pref[now][i]=pref[now][i-1]+(A[i]==now);
    }
}
ll fen[mxN];
void upd(int now, int x){while(now<=N)  fen[now]+=x, now+=(now&(-now));}
ll sum(int now)
{
    int ret=0;
    while(now)  ret+=fen[now], now-=(now&(-now));
    return ret;
}
ll solv(int s, int e){return sum(e)-sum(s-1);}
void init_inv()
{
    for(int i=K;i>=1;i--)
    {
        for(int x : v[i])   ans+=sum(x);
        for(int x : v[i])   upd(x, 1);
    }
}
ll minv(int a, int b)
{
    ll ret=0;
    assert(cnt[b]<M);
    for(int x : v[b])   ret+=pref[a][x];
    return ret;
}
ll sinv(int a, int b)
{
    ll ret=0, idx=0;
    for(int i=0;i<v[b].size();i++)
    {
        while(idx!=v[a].size() && v[a][idx]<v[b][i])    idx++;
        ret+=idx;
    }
    return ret;
}
ll inv(int a, int b)
{
    if(cnt[a]<cnt[b])   return cnt[a]*cnt[b]-inv(b, a);
    if(cnt[b]>=M)
    {
        if(a<b) return mp[pii(a, b)];
        else    return cnt[a]*cnt[b]-mp[pii(b, a)];
    }
    if(cnt[a]>=M && cnt[b]<M)   minv(a, b);
    else    return sinv(a, b);
}
int main()
{
    gibon
    cin >> N >> K >> Q;
    for(int i=1;i<=N;i++)   cin >> A[i], v[A[i]].push_back(i), cnt[A[i]]++;
    M=1;
    while((M+1)*(M+1)<=N)   M++;
    for(int i=1;i<=K;i++)   if(cnt[i]>=M)   big.push_back(i);
    make_bb();
    make_pref();
    init_inv();
    for(int i=1;i<=K;i++)   B[i]=i;
    while(Q--)
    {
        int a;
        cin >> a;
        ll ninv=inv(B[a+1], B[a]);
        ans-=ninv;
        ans+=cnt[B[a]]*cnt[B[a+1]]-ninv;
        swap(B[a], B[a+1]);
        cout << ans << '\n';
    }
}

Compilation message

Main.cpp: In function 'void make_bb()':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<big.size();i++)
      |                 ~^~~~~~~~~~~
Main.cpp:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j=i+1;j<big.size();j++)
      |                       ~^~~~~~~~~~~
Main.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             for(int k=0;k<v[n2].size();k++)
      |                         ~^~~~~~~~~~~~~
Main.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |                 while(idx!=v[n1].size() && v[n1][idx]<v[n2][k]) idx++;
      |                       ~~~^~~~~~~~~~~~~~
Main.cpp: In function 'll sinv(int, int)':
Main.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<v[b].size();i++)
      |                 ~^~~~~~~~~~~~
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(idx!=v[a].size() && v[a][idx]<v[b][i])    idx++;
      |               ~~~^~~~~~~~~~~~~
Main.cpp: In function 'll inv(int, int)':
Main.cpp:87:37: warning: control reaches end of non-void function [-Wreturn-type]
   87 |     if(cnt[a]>=M && cnt[b]<M)   minv(a, b);
      |                                 ~~~~^~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8216 KB Output is correct
2 Correct 14 ms 9044 KB Output is correct
3 Correct 117 ms 85500 KB Output is correct
4 Correct 14 ms 6812 KB Output is correct
5 Correct 16 ms 6996 KB Output is correct
6 Correct 22 ms 7084 KB Output is correct
7 Correct 28 ms 8172 KB Output is correct
8 Correct 28 ms 9212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 19340 KB Output is correct
2 Correct 166 ms 20364 KB Output is correct
3 Correct 261 ms 37332 KB Output is correct
4 Correct 388 ms 96580 KB Output is correct
5 Correct 2632 ms 17920 KB Output is correct
6 Correct 2137 ms 21884 KB Output is correct
7 Correct 2156 ms 21952 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -