oj.uz

Submission #469019

# Submission time Handle Problem Language Result Execution time Memory
469019 2021-08-30T12:02:34 Z stefantaga Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 1338 ms 524292 KB 
#include "bubblesort2.h"
#define INF 1000000
#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[2000005],lazy[2000005];
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;
}
int max1(int a,int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
void update(int st,int dr,int nod,int ua,int ub,int 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:85:9: warning: unused variable 'j' [-Wunused-variable]
   85 |     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 2 ms 460 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 6 ms 716 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 7 ms 708 KB Output is correct
14 Correct 5 ms 696 KB Output is correct
15 Correct 6 ms 716 KB Output is correct
16 Correct 5 ms 704 KB Output is correct
17 Correct 5 ms 588 KB Output is correct
18 Correct 7 ms 668 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 2 ms 460 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 6 ms 716 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 7 ms 708 KB Output is correct
14 Correct 5 ms 696 KB Output is correct
15 Correct 6 ms 716 KB Output is correct
16 Correct 5 ms 704 KB Output is correct
17 Correct 5 ms 588 KB Output is correct
18 Correct 7 ms 668 KB Output is correct
19 Correct 26 ms 1940 KB Output is correct
20 Correct 25 ms 2124 KB Output is correct
21 Correct 25 ms 2100 KB Output is correct
22 Correct 33 ms 2044 KB Output is correct
23 Correct 31 ms 1988 KB Output is correct
24 Correct 24 ms 1952 KB Output is correct
25 Correct 23 ms 1932 KB Output is correct
26 Correct 22 ms 1872 KB Output is correct
27 Correct 24 ms 1836 KB Output is correct
28 Correct 22 ms 1852 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3532 KB Output is correct
2 Correct 126 ms 7552 KB Output is correct
3 Correct 229 ms 12948 KB Output is correct
4 Correct 236 ms 12840 KB Output is correct
5 Correct 249 ms 12880 KB Output is correct
6 Correct 230 ms 12748 KB Output is correct
7 Correct 237 ms 12784 KB Output is correct
8 Correct 252 ms 12864 KB Output is correct
9 Correct 216 ms 12764 KB Output is correct
10 Correct 162 ms 8056 KB Output is correct
11 Correct 169 ms 8128 KB Output is correct
12 Correct 157 ms 8152 KB Output is correct
13 Correct 171 ms 8092 KB Output is correct
14 Correct 146 ms 8164 KB Output is correct
15 Correct 155 ms 8168 KB Output is correct
16 Correct 137 ms 8064 KB Output is correct
17 Correct 141 ms 8128 KB Output is correct
18 Correct 148 ms 8272 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 6 ms 716 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 6 ms 716 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 7 ms 708 KB Output is correct
14 Correct 5 ms 696 KB Output is correct
15 Correct 6 ms 716 KB Output is correct
16 Correct 5 ms 704 KB Output is correct
17 Correct 5 ms 588 KB Output is correct
18 Correct 7 ms 668 KB Output is correct
19 Correct 26 ms 1940 KB Output is correct
20 Correct 25 ms 2124 KB Output is correct
21 Correct 25 ms 2100 KB Output is correct
22 Correct 33 ms 2044 KB Output is correct
23 Correct 31 ms 1988 KB Output is correct
24 Correct 24 ms 1952 KB Output is correct
25 Correct 23 ms 1932 KB Output is correct
26 Correct 22 ms 1872 KB Output is correct
27 Correct 24 ms 1836 KB Output is correct
28 Correct 22 ms 1852 KB Output is correct
29 Correct 45 ms 3532 KB Output is correct
30 Correct 126 ms 7552 KB Output is correct
31 Correct 229 ms 12948 KB Output is correct
32 Correct 236 ms 12840 KB Output is correct
33 Correct 249 ms 12880 KB Output is correct
34 Correct 230 ms 12748 KB Output is correct
35 Correct 237 ms 12784 KB Output is correct
36 Correct 252 ms 12864 KB Output is correct
37 Correct 216 ms 12764 KB Output is correct
38 Correct 162 ms 8056 KB Output is correct
39 Correct 169 ms 8128 KB Output is correct
40 Correct 157 ms 8152 KB Output is correct
41 Correct 171 ms 8092 KB Output is correct
42 Correct 146 ms 8164 KB Output is correct
43 Correct 155 ms 8168 KB Output is correct
44 Correct 137 ms 8064 KB Output is correct
45 Correct 141 ms 8128 KB Output is correct
46 Correct 148 ms 8272 KB Output is correct
47 Correct 1040 ms 44312 KB Output is correct
48 Runtime error 1338 ms 524292 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -