Submission #283995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283995	2020-08-26T10:55:51 Z	Pyqe	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9000 ms	1284 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

long long n,as[500069],fw[500069],fi,inf=1e18;

void ud(long long x,long long w)
{
	for(fi=x;fi<=n;fi+=fi&-fi)
	{
		fw[fi]+=w;
	}
}

long long qr(long long lh,long long rh)
{
	long long z=0;
	
	for(fi=rh;fi;fi-=fi&-fi)
	{
		z+=fw[fi];
	}
	for(fi=lh-1;fi;fi-=fi&-fi)
	{
		z-=fw[fi];
	}
	return z;
}

vector<int> countScans(vector<int> a,vector<int> qp,vector<int> qw)
{
	long long t=qp.size(),rr,i,k,z;
	vector<int> sq;
	
	n=a.size();
	for(rr=0;rr<t;rr++)
	{
		a[qp[rr]]=qw[rr];
		for(i=0;i<n;i++)
		{
			as[i]=a[i];
			fw[i+1]=0;
		}
		sort(as,as+n);
		z=-inf;
		for(i=0;i<n;i++)
		{
			k=lower_bound(as,as+n,a[i])-as+1;
			z=max(z,qr(k+1,n));
			ud(k,1);
		}
		sq.push_back(z);
	}
	return sq;
}

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	384 KB	Output is correct
2	Correct	93 ms	428 KB	Output is correct
3	Correct	642 ms	632 KB	Output is correct
4	Correct	641 ms	632 KB	Output is correct
5	Correct	601 ms	516 KB	Output is correct
6	Correct	452 ms	628 KB	Output is correct
7	Correct	515 ms	504 KB	Output is correct
8	Correct	554 ms	632 KB	Output is correct
9	Correct	598 ms	504 KB	Output is correct
10	Correct	470 ms	508 KB	Output is correct
11	Correct	486 ms	504 KB	Output is correct
12	Correct	459 ms	504 KB	Output is correct
13	Correct	456 ms	504 KB	Output is correct
14	Correct	503 ms	624 KB	Output is correct
15	Correct	456 ms	496 KB	Output is correct
16	Correct	450 ms	632 KB	Output is correct
17	Correct	461 ms	632 KB	Output is correct
18	Correct	486 ms	504 KB	Output is correct

Subtask #2

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	384 KB	Output is correct
2	Correct	93 ms	428 KB	Output is correct
3	Correct	642 ms	632 KB	Output is correct
4	Correct	641 ms	632 KB	Output is correct
5	Correct	601 ms	516 KB	Output is correct
6	Correct	452 ms	628 KB	Output is correct
7	Correct	515 ms	504 KB	Output is correct
8	Correct	554 ms	632 KB	Output is correct
9	Correct	598 ms	504 KB	Output is correct
10	Correct	470 ms	508 KB	Output is correct
11	Correct	486 ms	504 KB	Output is correct
12	Correct	459 ms	504 KB	Output is correct
13	Correct	456 ms	504 KB	Output is correct
14	Correct	503 ms	624 KB	Output is correct
15	Correct	456 ms	496 KB	Output is correct
16	Correct	450 ms	632 KB	Output is correct
17	Correct	461 ms	632 KB	Output is correct
18	Correct	486 ms	504 KB	Output is correct
19	Execution timed out	9051 ms	816 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	9034 ms	1284 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	384 KB	Output is correct
2	Correct	93 ms	428 KB	Output is correct
3	Correct	642 ms	632 KB	Output is correct
4	Correct	641 ms	632 KB	Output is correct
5	Correct	601 ms	516 KB	Output is correct
6	Correct	452 ms	628 KB	Output is correct
7	Correct	515 ms	504 KB	Output is correct
8	Correct	554 ms	632 KB	Output is correct
9	Correct	598 ms	504 KB	Output is correct
10	Correct	470 ms	508 KB	Output is correct
11	Correct	486 ms	504 KB	Output is correct
12	Correct	459 ms	504 KB	Output is correct
13	Correct	456 ms	504 KB	Output is correct
14	Correct	503 ms	624 KB	Output is correct
15	Correct	456 ms	496 KB	Output is correct
16	Correct	450 ms	632 KB	Output is correct
17	Correct	461 ms	632 KB	Output is correct
18	Correct	486 ms	504 KB	Output is correct
19	Execution timed out	9051 ms	816 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-