oj.uz

Submission #741558

# Submission time Handle Problem Language Result Execution time Memory
741558 2023-05-14T10:31:23 Z MarwenElarbi Bubble Sort 2 (JOI18_bubblesort2) C++14
39 / 100
 146 ms 5836 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
#include <ext/pb_ds/assoc_container.hpp>
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9+7;
const int nax = 1e4+5;
const int MAX_VAL = 1e6;
double PI=3.14159265359;
int arx[8]={1,1,0,-1,-1,-1, 0, 1};
int ary[8]={0,1,1, 1, 0,-1,-1,-1};
/*typedef complex<int> Point;
#define X real()
#define Y imag()*/
/*void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}*/
vector<pair<ll,int>> tab(nax);
vi segtree(nax*4);
vi upd(nax*4);
void update(int left,int right,int value,int pos,int l,int r)
{
    if (l>=left&&r<=right){
        upd[pos]+=value;
        segtree[pos]+=value;
        return;
    }
    if (r<=left||l>=right) return;
    int mid=(l+r)/2;
    update(left,right,value,pos*2+1,l,mid);
    update(left,right,value,pos*2+2,mid,r);
    segtree[pos] = max(segtree[pos*2+1],segtree[pos*2+2])+upd[pos];
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
    int n,q;
    n=A.size();
    q=X.size();
    vi nabba;
    vi check(n+q);
    map<int,int> ind;
    for (int i = 0; i < n; ++i)
    {
        check[i]=A[i];
    }
    for (int i = 0; i < q; ++i)
    {
        check[i+n]=V[i];
    }
    sort(check.begin(),check.end());
    int cur=0;
    for (int i = 0; i < check.size(); ++i)
    {
        if (i==0)  {
            ind[check[i]]=cur;
            cur++;
        }
        else{
            if (check[i]==check[i-1]) {
                continue;
            }
            ind[check[i]]=cur;
            cur++;
        }
    }
    map<int,set<int>> pos;
    for (int i = 0; i < n; ++i)
    {
        pos[ind[A[i]]].insert(i);
        //cout << ind[A[i]]<<endl;
        update(ind[A[i]],cur,-1,0,0,nax*4);
    }
    for (int i = 0; i < cur; ++i)
    {
        if ((int)pos[i].size()>0){
            update(i,i+1,*pos[i].rbegin()+1,0,0,nax*4);
        }
    }
    for (int i = 0; i < q; ++i)
    {
        int x=X[i];
        int nw=V[i];
        int lst=A[x];
        A[x]=nw;
        lst=ind[lst];
        nw=ind[nw];
        int lstpos=*pos[lst].rbegin();
        pos[lst].erase(x);
        if ((int)pos[lst].size()>0) update(lst,lst+1,(*pos[lst].rbegin()-lstpos),0,0,nax*4);
        else update(lst,lst+1,-lstpos-1,0,0,nax*4);
        update(lst,cur,1,0,0,nax*4);
        if ((int)pos[nw].size()==0){
            pos[nw].insert(x);
            update(nw,nw+1,x+1,0,0,nax*4);
        }else{
            lstpos=*pos[nw].rbegin();
            pos[nw].insert(x);
            update(nw,nw+1,(*pos[nw].rbegin()-lstpos),0,0,nax*4);
        }
        update(nw,cur,-1,0,0,nax*4);
        nabba.pb(segtree[0]);
        //cout << segtree[0]<<endl;
    }
    return nabba;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < check.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 4 ms 1108 KB Output is correct
3 Correct 9 ms 1572 KB Output is correct
4 Correct 8 ms 1576 KB Output is correct
5 Correct 7 ms 1572 KB Output is correct
6 Correct 8 ms 1488 KB Output is correct
7 Correct 7 ms 1568 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 8 ms 1572 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 8 ms 1464 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 7 ms 1464 KB Output is correct
14 Correct 7 ms 1444 KB Output is correct
15 Correct 8 ms 1348 KB Output is correct
16 Correct 7 ms 1364 KB Output is correct
17 Correct 10 ms 1420 KB Output is correct
18 Correct 7 ms 1364 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 4 ms 1108 KB Output is correct
3 Correct 9 ms 1572 KB Output is correct
4 Correct 8 ms 1576 KB Output is correct
5 Correct 7 ms 1572 KB Output is correct
6 Correct 8 ms 1488 KB Output is correct
7 Correct 7 ms 1568 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 8 ms 1572 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 8 ms 1464 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 7 ms 1464 KB Output is correct
14 Correct 7 ms 1444 KB Output is correct
15 Correct 8 ms 1348 KB Output is correct
16 Correct 7 ms 1364 KB Output is correct
17 Correct 10 ms 1420 KB Output is correct
18 Correct 7 ms 1364 KB Output is correct
19 Runtime error 8 ms 3284 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2416 KB Output is correct
2 Correct 86 ms 4120 KB Output is correct
3 Correct 146 ms 5632 KB Output is correct
4 Correct 119 ms 5608 KB Output is correct
5 Correct 116 ms 5660 KB Output is correct
6 Correct 117 ms 5668 KB Output is correct
7 Correct 120 ms 5664 KB Output is correct
8 Correct 119 ms 5720 KB Output is correct
9 Correct 113 ms 5668 KB Output is correct
10 Correct 90 ms 5700 KB Output is correct
11 Correct 87 ms 5696 KB Output is correct
12 Correct 86 ms 5828 KB Output is correct
13 Correct 95 ms 5708 KB Output is correct
14 Correct 90 ms 5676 KB Output is correct
15 Correct 87 ms 5696 KB Output is correct
16 Correct 88 ms 5836 KB Output is correct
17 Correct 88 ms 5700 KB Output is correct
18 Correct 87 ms 5804 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 4 ms 1108 KB Output is correct
3 Correct 9 ms 1572 KB Output is correct
4 Correct 8 ms 1576 KB Output is correct
5 Correct 7 ms 1572 KB Output is correct
6 Correct 8 ms 1488 KB Output is correct
7 Correct 7 ms 1568 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 8 ms 1572 KB Output is correct
10 Correct 8 ms 1492 KB Output is correct
11 Correct 8 ms 1464 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 7 ms 1464 KB Output is correct
14 Correct 7 ms 1444 KB Output is correct
15 Correct 8 ms 1348 KB Output is correct
16 Correct 7 ms 1364 KB Output is correct
17 Correct 10 ms 1420 KB Output is correct
18 Correct 7 ms 1364 KB Output is correct
19 Runtime error 8 ms 3284 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -