oj.uz

Submission #469025

# Submission time Handle Problem Language Result Execution time Memory
469025 2021-08-30T12:05:07 Z stefantaga Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 4296 ms 124728 KB 
#include "bubblesort2.h"
#define INF 10000000000000
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
int nr,n,i,v[500005];
map <pair <int,int> ,int> m;
long long arb[4000005],lazy[4000005];
void propaga(int st,int dr,int nod)
{
    if (st==dr)
    {
        return;
    }
    if (lazy[nod]==0)
    {
        return;
    }
    lazy[2*nod]+=lazy[nod];
    lazy[2*nod+1]+=lazy[nod];
    arb[2*nod]+=lazy[nod];
    arb[2*nod+1]+=lazy[nod];
    lazy[nod]=0;
    return;
}
void update(int st,int dr,int nod,int ua,int ub,long long val)
{
    if (ua<=st&&dr<=ub)
    {
        arb[nod]+=val;
        lazy[nod]+=val;
        return ;
    }
    propaga(st,dr,nod);
    int mij=(st+dr)/2;
    if (ua<=mij)
    {
        update(st,mij,2*nod,ua,ub,val);
    }
    if (mij<ub)
    {
        update(mij+1,dr,2*nod+1,ua,ub,val);
    }
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> val){
	int q=X.size();
	n=A.size();
	for (i=0;i<n;i++)
    {
        v[i+1]=A[i];
    }
    for (i=1;i<=n;i++)
    {
        m[{v[i],i}]=1;
    }
    for (i=0;i<q;i++)
    {
        m[{val[i],X[i]+1}]=1;
    }
    nr=0;
    for (auto ind: m)
    {
        nr++;
        m[ind.first]=nr;
    }
    update(1,nr,1,1,nr,-INF);
    for (i=1;i<=n;i++)
    {
        v[i]=m[{v[i],i}];
        update(1,nr,1,v[i],v[i],INF+i);
        update(1,nr,1,v[i]+1,nr,-1);
    }
    int j;
    vector <int> sol;
    for (i=0;i<q;i++)
    {
        int poz=X[i]+1;
        update(1,nr,1,v[poz],v[poz],-INF-poz);
        update(1,nr,1,v[poz]+1,nr,1);
        v[poz]=m[{val[i],poz}];
        update(1,nr,1,v[poz],v[poz],INF+poz);
        update(1,nr,1,v[poz]+1,nr,-1);
        sol.push_back(arb[1]-1);
    }
    return sol;
}


















/*int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();

	std::vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();

	std::vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}

	std::vector<int> res=countScans(A,X,V);

	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:77:9: warning: unused variable 'j' [-Wunused-variable]
   77 |     int j;
      |         ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 6 ms 716 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 5 ms 716 KB Output is correct
15 Correct 5 ms 672 KB Output is correct
16 Correct 5 ms 688 KB Output is correct
17 Correct 6 ms 716 KB Output is correct
18 Correct 6 ms 588 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 6 ms 716 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 5 ms 716 KB Output is correct
15 Correct 5 ms 672 KB Output is correct
16 Correct 5 ms 688 KB Output is correct
17 Correct 6 ms 716 KB Output is correct
18 Correct 6 ms 588 KB Output is correct
19 Correct 22 ms 1964 KB Output is correct
20 Correct 26 ms 2088 KB Output is correct
21 Correct 25 ms 2128 KB Output is correct
22 Correct 27 ms 2116 KB Output is correct
23 Correct 23 ms 1948 KB Output is correct
24 Correct 23 ms 1988 KB Output is correct
25 Correct 22 ms 1920 KB Output is correct
26 Correct 26 ms 1936 KB Output is correct
27 Correct 22 ms 1808 KB Output is correct
28 Correct 24 ms 1836 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3540 KB Output is correct
2 Correct 139 ms 7440 KB Output is correct
3 Correct 248 ms 12332 KB Output is correct
4 Correct 229 ms 12328 KB Output is correct
5 Correct 238 ms 12284 KB Output is correct
6 Correct 216 ms 12160 KB Output is correct
7 Correct 241 ms 12384 KB Output is correct
8 Correct 234 ms 12180 KB Output is correct
9 Correct 223 ms 12228 KB Output is correct
10 Correct 180 ms 7576 KB Output is correct
11 Correct 156 ms 7464 KB Output is correct
12 Correct 156 ms 7468 KB Output is correct
13 Correct 147 ms 7472 KB Output is correct
14 Correct 154 ms 7536 KB Output is correct
15 Correct 149 ms 7492 KB Output is correct
16 Correct 135 ms 7492 KB Output is correct
17 Correct 139 ms 7544 KB Output is correct
18 Correct 136 ms 7624 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 6 ms 748 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 6 ms 716 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 5 ms 716 KB Output is correct
14 Correct 5 ms 716 KB Output is correct
15 Correct 5 ms 672 KB Output is correct
16 Correct 5 ms 688 KB Output is correct
17 Correct 6 ms 716 KB Output is correct
18 Correct 6 ms 588 KB Output is correct
19 Correct 22 ms 1964 KB Output is correct
20 Correct 26 ms 2088 KB Output is correct
21 Correct 25 ms 2128 KB Output is correct
22 Correct 27 ms 2116 KB Output is correct
23 Correct 23 ms 1948 KB Output is correct
24 Correct 23 ms 1988 KB Output is correct
25 Correct 22 ms 1920 KB Output is correct
26 Correct 26 ms 1936 KB Output is correct
27 Correct 22 ms 1808 KB Output is correct
28 Correct 24 ms 1836 KB Output is correct
29 Correct 43 ms 3540 KB Output is correct
30 Correct 139 ms 7440 KB Output is correct
31 Correct 248 ms 12332 KB Output is correct
32 Correct 229 ms 12328 KB Output is correct
33 Correct 238 ms 12284 KB Output is correct
34 Correct 216 ms 12160 KB Output is correct
35 Correct 241 ms 12384 KB Output is correct
36 Correct 234 ms 12180 KB Output is correct
37 Correct 223 ms 12228 KB Output is correct
38 Correct 180 ms 7576 KB Output is correct
39 Correct 156 ms 7464 KB Output is correct
40 Correct 156 ms 7468 KB Output is correct
41 Correct 147 ms 7472 KB Output is correct
42 Correct 154 ms 7536 KB Output is correct
43 Correct 149 ms 7492 KB Output is correct
44 Correct 135 ms 7492 KB Output is correct
45 Correct 139 ms 7544 KB Output is correct
46 Correct 136 ms 7624 KB Output is correct
47 Correct 993 ms 40540 KB Output is correct
48 Correct 3980 ms 116916 KB Output is correct
49 Correct 4130 ms 124444 KB Output is correct
50 Correct 4296 ms 124520 KB Output is correct
51 Correct 4148 ms 124428 KB Output is correct
52 Correct 4127 ms 124564 KB Output is correct
53 Correct 4188 ms 124532 KB Output is correct
54 Correct 3876 ms 124604 KB Output is correct
55 Correct 4065 ms 124596 KB Output is correct
56 Correct 3653 ms 124648 KB Output is correct
57 Correct 4097 ms 124712 KB Output is correct
58 Correct 3781 ms 124728 KB Output is correct
59 Correct 3548 ms 115484 KB Output is correct
60 Correct 3489 ms 115400 KB Output is correct
61 Correct 3567 ms 115376 KB Output is correct
62 Correct 3522 ms 111384 KB Output is correct
63 Correct 3563 ms 111432 KB Output is correct
64 Correct 3322 ms 111420 KB Output is correct
65 Correct 3279 ms 107444 KB Output is correct
66 Correct 3181 ms 107340 KB Output is correct
67 Correct 3189 ms 107396 KB Output is correct