oj.uz

Submission #97815

# Submission time Handle Problem Language Result Execution time Memory
97815 2019-02-18T16:19:15 Z scanhex Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 37360 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int N=500500;
int a[N];
int n;
set<pair<int,int>>all;
int sz1=0;
int sz2=2000;

int memos[N];

void reb_int(){
}
struct fen1{
	vector<int>ys;
	vector<int>t;
	int n;
	void init(){
		t.resize(ys.size());
		sort(ys.begin(),ys.end());
		ys.erase(unique(ys.begin(),ys.end()),ys.end());
		n=t.size();
	}
	int get(int r){
		r=lower_bound(ys.begin(),ys.end(),r)-ys.begin();
		--r;
		int ans=0;
		for(;r>=0;r&=r+1,r--)
			ans+=t[r];
		return ans;
	}
	void ch(int x,int y){
		x=lower_bound(ys.begin(),ys.end(),x)-ys.begin();
		for(;x<n;x|=x+1)
			t[x]+=y;
	}
	int get(int l,int r){
		return get(r)-get(l);
	}
} fens[N];

void ch(int x,int y,int val){
	for(;x<N;x|=x+1)
		fens[x].ch(y,val);
}

void recalc(int i){
	int ans=i;
	int r=i-1;
//	cerr<<fens[0].t[0]<<' '<<fens[1].t[0]<<' '<<fens[1].t[1]<<'\n';
	for(;r>=0;r&=r+1,--r){
		ans-=fens[r].get(0,a[i]+1);
	}
	memos[i]=ans;
}

vector<pair<int,int>>pts;
void init_fens(){
	int ptr=0;
	for(int i=0;i<n;++i){
		while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
		for(int k=i;k<n;k|=k+1)
			for(int j=ptr;j<pts.size()&&pts[j].first==i;++j)
				fens[k].ys.push_back(pts[j].second);
	}
	for(int i=0;i<n;++i){
		fens[i].init();
	}
}

int cnt=0;


void upd(int i,int coef){
	auto p=make_pair(a[i],i);
	ch(i,a[i],coef);
	if(coef==-1)
		all.erase(p);
	if(coef==1)
		all.insert(p);
	/*
	vector<int>kek;
	auto it=all.begin();
	for(int i=0;i<sz2;++i,++it){
		kek.push_back(it->second);
	}
	for(int i=0;i<sz1;++i)kek.push_back(n-i-1);
	sort(kek.begin(),kek.end());
	kek.erase(unique(kek.begin(),kek.end()),kek.end());
	for(int x:kek){
		if(i<x&&a[i]>a[x])memos[x]+=coef;
	}
	*/
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> x,std::vector<int> v){
	n=A.size();
	sz1=min(sz1,n);
	sz2=min(sz2,n);
	int q=x.size();
	copy(A.begin(),A.end(),a);
	for(int i=0;i<n;++i){
		pts.emplace_back(i,a[i]);
	}
	for(int i=0;i<q;++i)pts.emplace_back(x[i],v[i]);
	sort(pts.begin(),pts.end());
	init_fens();
	for(int i=0;i<n;++i)upd(i,1);
	vector<int>answer(q);
	for(int i=0;i<q;++i){
		upd(x[i],-1);
		a[x[i]]=v[i];
		upd(x[i],1);
		recalc(x[i]);
		for(int j=0;j<sz1;++j){
			recalc(n-j-1);
			answer[i]=max(answer[i],memos[n-j-1]);
		}
		auto it=all.begin();
		for(int j=0;j<sz2;++j,++it){
			recalc(it->second);
			answer[i]=max(answer[i],memos[it->second]);
		}
	}
	return answer;
}

Compilation message

bubblesort2.cpp: In function 'void init_fens()':
bubblesort2.cpp:64:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
         ~~~^~~~~~~~~~~
bubblesort2.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=ptr;j<pts.size()&&pts[j].first==i;++j)
                  ~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 28024 KB Output is correct
2 Correct 251 ms 28024 KB Output is correct
3 Correct 1638 ms 28272 KB Output is correct
4 Correct 1569 ms 28280 KB Output is correct
5 Correct 1629 ms 28280 KB Output is correct
6 Correct 1197 ms 28408 KB Output is correct
7 Correct 1281 ms 28288 KB Output is correct
8 Correct 1494 ms 28288 KB Output is correct
9 Correct 1710 ms 28280 KB Output is correct
10 Correct 1060 ms 28276 KB Output is correct
11 Correct 1072 ms 28276 KB Output is correct
12 Correct 1162 ms 28356 KB Output is correct
13 Correct 1014 ms 28276 KB Output is correct
14 Correct 1042 ms 28280 KB Output is correct
15 Correct 1185 ms 28280 KB Output is correct
16 Correct 950 ms 28408 KB Output is correct
17 Correct 1029 ms 28288 KB Output is correct
18 Correct 972 ms 28380 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 28024 KB Output is correct
2 Correct 251 ms 28024 KB Output is correct
3 Correct 1638 ms 28272 KB Output is correct
4 Correct 1569 ms 28280 KB Output is correct
5 Correct 1629 ms 28280 KB Output is correct
6 Correct 1197 ms 28408 KB Output is correct
7 Correct 1281 ms 28288 KB Output is correct
8 Correct 1494 ms 28288 KB Output is correct
9 Correct 1710 ms 28280 KB Output is correct
10 Correct 1060 ms 28276 KB Output is correct
11 Correct 1072 ms 28276 KB Output is correct
12 Correct 1162 ms 28356 KB Output is correct
13 Correct 1014 ms 28276 KB Output is correct
14 Correct 1042 ms 28280 KB Output is correct
15 Correct 1185 ms 28280 KB Output is correct
16 Correct 950 ms 28408 KB Output is correct
17 Correct 1029 ms 28288 KB Output is correct
18 Correct 972 ms 28380 KB Output is correct
19 Correct 7036 ms 29608 KB Output is correct
20 Correct 8981 ms 29848 KB Output is correct
21 Incorrect 4914 ms 30052 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1480 ms 33268 KB Output is correct
2 Execution timed out 9053 ms 37360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 28024 KB Output is correct
2 Correct 251 ms 28024 KB Output is correct
3 Correct 1638 ms 28272 KB Output is correct
4 Correct 1569 ms 28280 KB Output is correct
5 Correct 1629 ms 28280 KB Output is correct
6 Correct 1197 ms 28408 KB Output is correct
7 Correct 1281 ms 28288 KB Output is correct
8 Correct 1494 ms 28288 KB Output is correct
9 Correct 1710 ms 28280 KB Output is correct
10 Correct 1060 ms 28276 KB Output is correct
11 Correct 1072 ms 28276 KB Output is correct
12 Correct 1162 ms 28356 KB Output is correct
13 Correct 1014 ms 28276 KB Output is correct
14 Correct 1042 ms 28280 KB Output is correct
15 Correct 1185 ms 28280 KB Output is correct
16 Correct 950 ms 28408 KB Output is correct
17 Correct 1029 ms 28288 KB Output is correct
18 Correct 972 ms 28380 KB Output is correct
19 Correct 7036 ms 29608 KB Output is correct
20 Correct 8981 ms 29848 KB Output is correct
21 Incorrect 4914 ms 30052 KB Output isn't correct
22 Halted 0 ms 0 KB -