oj.uz

Submission #854297

# Submission time Handle Problem Language Result Execution time Memory
854297 2023-09-26T16:55:49 Z Lobo Swap Swap Sort (CCO21_day1problem1) C++17
25 / 25
 798 ms 174920 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
const int B = 80;
 
int n, k, q, a[maxn], id[maxn], cntid, tr[4*maxn];
vector<int> fq[maxn];
vector<vector<int>> inv;
 
void upd(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        tr[no]+= val;
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    upd(lc,l,mid,pos,val);
    upd(rc,mid+1,r,pos,val);
    tr[no] = tr[lc]+tr[rc];
}
 
int qry(int no, int l, int r, int ll, int rr) {
    if(l > rr || r < ll) return 0;
    if(l >= ll && r <= rr) return tr[no];
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return qry(lc,l,mid,ll,rr)+qry(rc,mid+1,r,ll,rr);
}
 
void solve() {
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        fq[a[i]].pb(i);
    }
 
 
    for(int x = 1; x <= k; x++) {
        if(fq[x].size() >= B) {
            id[x] = cntid++;
            inv.pb(vector<int>(k+1,0));
 
            int cntafter = fq[x].size();
            for(int i = 1; i <= n; i++) {
                if(a[i] == x) cntafter--;
                else {
                    inv[id[x]][a[i]]+= cntafter;
                }
            }
        }
    }
 
    int invcur = 0;
    for(int i = 1; i <= n; i++) {
        invcur+= qry(1,1,k,a[i]+1,k);
        upd(1,1,k,a[i],1);
    }
 
    vector<int> p(k+1); for(int i = 1; i <= k; i++) p[i] = i;
 
    for(int i = 1; i <= q; i++) {
        int j; cin >> j;
        int l = p[j];
        int r = p[j+1];
 
        int lr,rl;
 
        if(fq[l].size() >= B) {
            lr = inv[id[l]][r];
            rl = fq[l].size()*fq[r].size() - lr;
        }
        else if(fq[r].size() >= B) {
            rl = inv[id[r]][l];
            lr = fq[l].size()*fq[r].size() - rl;
        }
        else {
            int cntr = 0;
            lr = 0;
            int pl = 0;
            int pr = 0;
            while(pl != fq[l].size() || pr != fq[r].size()) {
                if(pr == fq[r].size() || (pl != fq[l].size() && fq[l][pl] < fq[r][pr])) {
                    lr+= cntr;
                    pl++;
                }
                else {
                    cntr++;
                    pr++;
                }
            }
            rl = fq[l].size()*fq[r].size() - lr;
        }
 
        invcur+= -lr+rl;
        swap(p[j],p[j+1]);
        cout << invcur << endl;
    }
 
}
    
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }
 
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:90:22: 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]
   90 |             while(pl != fq[l].size() || pr != fq[r].size()) {
      |                   ~~~^~~~~~~~~~~~~~~
Main.cpp:90: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]
   90 |             while(pl != fq[l].size() || pr != fq[r].size()) {
      |                                         ~~~^~~~~~~~~~~~~~~
Main.cpp:91:23: 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]
   91 |                 if(pr == fq[r].size() || (pl != fq[l].size() && fq[l][pl] < fq[r][pr])) {
      |                    ~~~^~~~~~~~~~~~~~~
Main.cpp:91:46: 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]
   91 |                 if(pr == fq[r].size() || (pl != fq[l].size() && fq[l][pl] < fq[r][pr])) {
      |                                           ~~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8396 KB Output is correct
2 Correct 9 ms 8660 KB Output is correct
3 Correct 29 ms 8536 KB Output is correct
4 Correct 148 ms 16164 KB Output is correct
5 Correct 29 ms 8792 KB Output is correct
6 Correct 32 ms 8792 KB Output is correct
7 Correct 40 ms 9504 KB Output is correct
8 Correct 43 ms 10324 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 19412 KB Output is correct
2 Correct 124 ms 19252 KB Output is correct
3 Correct 134 ms 19416 KB Output is correct
4 Correct 152 ms 19536 KB Output is correct
5 Correct 212 ms 20956 KB Output is correct
6 Correct 212 ms 21500 KB Output is correct
7 Correct 227 ms 21492 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 5 ms 6744 KB Output is correct
8 Correct 4 ms 6744 KB Output is correct
9 Correct 11 ms 8396 KB Output is correct
10 Correct 9 ms 8660 KB Output is correct
11 Correct 29 ms 8536 KB Output is correct
12 Correct 148 ms 16164 KB Output is correct
13 Correct 29 ms 8792 KB Output is correct
14 Correct 32 ms 8792 KB Output is correct
15 Correct 40 ms 9504 KB Output is correct
16 Correct 43 ms 10324 KB Output is correct
17 Correct 116 ms 19412 KB Output is correct
18 Correct 124 ms 19252 KB Output is correct
19 Correct 134 ms 19416 KB Output is correct
20 Correct 152 ms 19536 KB Output is correct
21 Correct 212 ms 20956 KB Output is correct
22 Correct 212 ms 21500 KB Output is correct
23 Correct 227 ms 21492 KB Output is correct
24 Correct 307 ms 27292 KB Output is correct
25 Correct 707 ms 19756 KB Output is correct
26 Correct 417 ms 19872 KB Output is correct
27 Correct 317 ms 19912 KB Output is correct
28 Correct 303 ms 20096 KB Output is correct
29 Correct 246 ms 20500 KB Output is correct
30 Correct 228 ms 21444 KB Output is correct
31 Correct 243 ms 21388 KB Output is correct
32 Correct 177 ms 30288 KB Output is correct
33 Correct 200 ms 20980 KB Output is correct
34 Correct 212 ms 21528 KB Output is correct
35 Correct 253 ms 22620 KB Output is correct
36 Correct 291 ms 27212 KB Output is correct
37 Correct 628 ms 21912 KB Output is correct
38 Correct 567 ms 19848 KB Output is correct
39 Correct 244 ms 21264 KB Output is correct
40 Correct 213 ms 27564 KB Output is correct
41 Correct 216 ms 35296 KB Output is correct
42 Correct 198 ms 36692 KB Output is correct
43 Correct 222 ms 44452 KB Output is correct
44 Correct 211 ms 50872 KB Output is correct
45 Correct 205 ms 52364 KB Output is correct
46 Correct 337 ms 21072 KB Output is correct
47 Correct 459 ms 21076 KB Output is correct
48 Correct 798 ms 174920 KB Output is correct
49 Correct 675 ms 56712 KB Output is correct
50 Correct 180 ms 28780 KB Output is correct
51 Correct 198 ms 28496 KB Output is correct
52 Correct 175 ms 28432 KB Output is correct
53 Correct 182 ms 28792 KB Output is correct
54 Correct 179 ms 28708 KB Output is correct
55 Correct 1 ms 7000 KB Output is correct