oj.uz

Submission #71352

# Submission time Handle Problem Language Result Execution time Memory
71352 2018-08-24T11:42:44 Z KLPP Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 319 ms 159564 KB 
#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int lld;
typedef std::map<lld,int>::iterator mit;
#define INF 1000000000000000
class FT{
	int arr[100000];
	int n;
	public:
	void init(int N){
		n=N;
		for(int i=0;i<=n;i++){
			arr[i]=0;
		}
	}
	int query(int prefix){
		prefix++;
		int ans=0;
		for(;prefix>0;prefix-=(prefix&(-prefix))){
			ans+=arr[prefix];
		}return ans;
	}
	void update(int pos){
		pos++;
		for(;pos<=n;pos+=(pos&(-pos))){
			arr[pos]++;
		}
	}
	void update2(int pos){
		pos++;
		for(;pos<=n;pos+=(pos&(-pos))){
			arr[pos]--;
		}
	}
	void print(){
		for(int i=0;i<=n;i++){
			cout<<arr[i]<<" ";
		}cout<<endl;
	}
};
FT *F;
int compute(vector<int> v){
	int n=v.size();
	F->init(n);
	pair<int,int> arr[n];
	for(int i=0;i<n;i++){
		arr[i]=pair<int,int>(v[i],i);
	}sort(arr,arr+n);
	int prev=n-1;
	int ans=0;
	for(int i=n-1;i>-1;i--){
		if(i==0 || arr[i-1]!=arr[i]){
			for(int j=prev;j>=i;j--){
				ans=max(ans,F->query(arr[j].second));
			}
			for(int j=prev;j>=i;j--){
				F->update(arr[j].second);
			}
			prev=i-1;
		}
	}
	return ans;
}
class LP{
	lld segtree[4000000];
	lld lazy[4000000];
	int n;
	public:
	void build(int a, int b, int node){//cout<<a<<" "<<b<<endl;
		lazy[node]=0;
		if(a==b){
			segtree[node]=-INF;
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		segtree[node]=max(segtree[2*node],segtree[2*node+1]);
	}
	void init(int N){
		n=N;
		build(0,n-1,1);
	}
	void extend(int node){
		segtree[node]+=lazy[node];
		
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		
		lazy[node]=0;
	}
	void update(int x, int y, lld val, int a, int b, int node){
		
		if(y<a || b<x)return;
		//cout<<x<<" "<<y<<" "<<a<<" "<<b<<" "<<node<<endl;
		if(x<=a && b<=y){
			lazy[node]+=val;
			return;
		}extend(node);
		int mid=(a+b)/2;
		update(x,y,val,a,mid,2*node);
		update(x,y,val,mid+1,b,2*node+1);
		segtree[node]=max(segtree[2*node]+lazy[2*node],segtree[2*node+1]+lazy[2*node+1]);
	}
	void Update(int x, int y, int val){
		if(x>y)return;
		update(x,y,val,0,n-1,1);
	}
	void set(int pos,lld val,int a, int b, int node){
		
		if(pos<a || pos>b)return;
		if(a==b){
			segtree[node]=val;
			lazy[node]=0;
			return;
		}extend(node);
		int mid=(a+b)/2;
		set(pos,val,a,mid,2*node);
		set(pos,val,mid+1,b,2*node+1);
		segtree[node]=max(segtree[2*node]+lazy[2*node],segtree[2*node+1]+lazy[2*node+1]);
	}
	void Set(int pos, lld val){
		set(pos,val,0,n-1,1);
	}
	lld query(){
		return segtree[1]+lazy[1];
	}
	void print(){
		for(int i=1;i<=2*n;i++){
			cout<<segtree[i]<<" "<<lazy[i]<<"   ";
		}cout<<endl;
	}
};
vector<lld> values;
int BSpos(lld x){
	int lo,hi;
	lo=-1;
	hi=values.size();
	while(hi-lo>1){
		int mid=(hi+lo)/2;
		if(values[mid]>x)hi=mid;
		else lo=mid;
	}
	if(values[lo]==x)return lo;
	return -1;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	LP *L;
	int n=A.size();
	L=new LP();
	
	vector<int> ans;
	vector<lld>a;
	vector<lld>v;
	for(int i=0;i<n;i++)a.push_back(A[i]);
	int Q=X.size();
	for(int i=0;i<Q;i++)v.push_back(V[i]);
	for(int i=0;i<n;i++)values.push_back((lld)a[i]*1000000+i);
	for(int i=0;i<Q;i++)values.push_back((lld)v[i]*1000000+X[i]);
	sort(values.begin(),values.end());
	FT *F;
	F=new FT();
	for(int i=0;i<n;i++)a[i]=a[i]*1000000+i;
	for(int i=0;i<Q;i++)v[i]=v[i]*1000000+X[i];
	F->init(n+Q);
	for(int i=0;i<n;i++){
		int pos=BSpos(a[i]);
 
		F->update(pos);
 
	}L->init(n+Q);
	for(int i=0;i<n;i++){//cout<<i<<" 1"<<endl;
		int pos=BSpos(a[i]);
		//cout<<pos<<endl;
		lld questao=F->query(pos)-1;
		//cout<<i-questao<<endl;
		L->Set(pos,i-questao);
	}
	//L->print();
	//cout<<L->query()<<endl;
	for(int i=0;i<Q;i++){//cout<<i<<" 2"<<endl;
		int pos1=BSpos(a[X[i]]);
		int pos2=BSpos(v[i]);
		F->update2(pos1);
		F->update(pos2);
		int start,end;
		
		lld query=F->query(pos2)-1;
		L->Set(pos1,-INF);
		//cout<<X[i]-query<<endl;
		L->Set(pos2,X[i]-query);
		//cout<<pos1<<" "<<pos2<<endl;
		L->Update(pos2+1,n+Q-1,-1);
		L->Update(pos1+1,n+Q-1,1);
		//cout<<L->query()<<endl;
		//L->print();
		ans.push_back(L->query());
		a[X[i]]=v[i];
	}
	return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:191:7: warning: unused variable 'start' [-Wunused-variable]
   int start,end;
       ^~~~~
bubblesort2.cpp:191:13: warning: unused variable 'end' [-Wunused-variable]
   int start,end;
             ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 63316 KB Output is correct
2 Correct 54 ms 63468 KB Output is correct
3 Correct 63 ms 63672 KB Output is correct
4 Correct 65 ms 63796 KB Output is correct
5 Correct 63 ms 64020 KB Output is correct
6 Correct 63 ms 64032 KB Output is correct
7 Correct 69 ms 64032 KB Output is correct
8 Correct 55 ms 64032 KB Output is correct
9 Correct 70 ms 64192 KB Output is correct
10 Correct 68 ms 64256 KB Output is correct
11 Correct 65 ms 64296 KB Output is correct
12 Correct 67 ms 64296 KB Output is correct
13 Correct 56 ms 64296 KB Output is correct
14 Correct 68 ms 64416 KB Output is correct
15 Correct 76 ms 64416 KB Output is correct
16 Correct 66 ms 64416 KB Output is correct
17 Correct 73 ms 64416 KB Output is correct
18 Correct 66 ms 64468 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 63316 KB Output is correct
2 Correct 54 ms 63468 KB Output is correct
3 Correct 63 ms 63672 KB Output is correct
4 Correct 65 ms 63796 KB Output is correct
5 Correct 63 ms 64020 KB Output is correct
6 Correct 63 ms 64032 KB Output is correct
7 Correct 69 ms 64032 KB Output is correct
8 Correct 55 ms 64032 KB Output is correct
9 Correct 70 ms 64192 KB Output is correct
10 Correct 68 ms 64256 KB Output is correct
11 Correct 65 ms 64296 KB Output is correct
12 Correct 67 ms 64296 KB Output is correct
13 Correct 56 ms 64296 KB Output is correct
14 Correct 68 ms 64416 KB Output is correct
15 Correct 76 ms 64416 KB Output is correct
16 Correct 66 ms 64416 KB Output is correct
17 Correct 73 ms 64416 KB Output is correct
18 Correct 66 ms 64468 KB Output is correct
19 Correct 68 ms 65040 KB Output is correct
20 Correct 86 ms 65292 KB Output is correct
21 Correct 73 ms 65460 KB Output is correct
22 Correct 96 ms 65680 KB Output is correct
23 Correct 89 ms 65924 KB Output is correct
24 Correct 79 ms 66040 KB Output is correct
25 Correct 77 ms 66204 KB Output is correct
26 Correct 79 ms 66384 KB Output is correct
27 Correct 77 ms 66480 KB Output is correct
28 Correct 77 ms 66636 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 67108 KB Output is correct
2 Correct 175 ms 68564 KB Output is correct
3 Correct 295 ms 70348 KB Output is correct
4 Correct 239 ms 70664 KB Output is correct
5 Correct 279 ms 71360 KB Output is correct
6 Correct 273 ms 71932 KB Output is correct
7 Correct 285 ms 72448 KB Output is correct
8 Correct 282 ms 73092 KB Output is correct
9 Correct 272 ms 73800 KB Output is correct
10 Correct 319 ms 74304 KB Output is correct
11 Correct 226 ms 74976 KB Output is correct
12 Correct 245 ms 75608 KB Output is correct
13 Correct 193 ms 76220 KB Output is correct
14 Correct 241 ms 76992 KB Output is correct
15 Correct 221 ms 77636 KB Output is correct
16 Correct 200 ms 78152 KB Output is correct
17 Correct 184 ms 78916 KB Output is correct
18 Correct 229 ms 79416 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 63316 KB Output is correct
2 Correct 54 ms 63468 KB Output is correct
3 Correct 63 ms 63672 KB Output is correct
4 Correct 65 ms 63796 KB Output is correct
5 Correct 63 ms 64020 KB Output is correct
6 Correct 63 ms 64032 KB Output is correct
7 Correct 69 ms 64032 KB Output is correct
8 Correct 55 ms 64032 KB Output is correct
9 Correct 70 ms 64192 KB Output is correct
10 Correct 68 ms 64256 KB Output is correct
11 Correct 65 ms 64296 KB Output is correct
12 Correct 67 ms 64296 KB Output is correct
13 Correct 56 ms 64296 KB Output is correct
14 Correct 68 ms 64416 KB Output is correct
15 Correct 76 ms 64416 KB Output is correct
16 Correct 66 ms 64416 KB Output is correct
17 Correct 73 ms 64416 KB Output is correct
18 Correct 66 ms 64468 KB Output is correct
19 Correct 68 ms 65040 KB Output is correct
20 Correct 86 ms 65292 KB Output is correct
21 Correct 73 ms 65460 KB Output is correct
22 Correct 96 ms 65680 KB Output is correct
23 Correct 89 ms 65924 KB Output is correct
24 Correct 79 ms 66040 KB Output is correct
25 Correct 77 ms 66204 KB Output is correct
26 Correct 79 ms 66384 KB Output is correct
27 Correct 77 ms 66480 KB Output is correct
28 Correct 77 ms 66636 KB Output is correct
29 Correct 83 ms 67108 KB Output is correct
30 Correct 175 ms 68564 KB Output is correct
31 Correct 295 ms 70348 KB Output is correct
32 Correct 239 ms 70664 KB Output is correct
33 Correct 279 ms 71360 KB Output is correct
34 Correct 273 ms 71932 KB Output is correct
35 Correct 285 ms 72448 KB Output is correct
36 Correct 282 ms 73092 KB Output is correct
37 Correct 272 ms 73800 KB Output is correct
38 Correct 319 ms 74304 KB Output is correct
39 Correct 226 ms 74976 KB Output is correct
40 Correct 245 ms 75608 KB Output is correct
41 Correct 193 ms 76220 KB Output is correct
42 Correct 241 ms 76992 KB Output is correct
43 Correct 221 ms 77636 KB Output is correct
44 Correct 200 ms 78152 KB Output is correct
45 Correct 184 ms 78916 KB Output is correct
46 Correct 229 ms 79416 KB Output is correct
47 Runtime error 307 ms 159564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -