oj.uz

Submission #97814

# Submission time Handle Problem Language Result Execution time Memory
97814 2019-02-18T16:18:07 Z scanhex Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 37616 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=2000;
int sz2=0;

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 125 ms 27896 KB Output is correct
2 Correct 238 ms 28172 KB Output is correct
3 Correct 1642 ms 28280 KB Output is correct
4 Correct 1596 ms 28280 KB Output is correct
5 Correct 1551 ms 28280 KB Output is correct
6 Correct 1078 ms 28280 KB Output is correct
7 Correct 1276 ms 28408 KB Output is correct
8 Correct 1443 ms 28288 KB Output is correct
9 Correct 1555 ms 28308 KB Output is correct
10 Correct 1051 ms 28280 KB Output is correct
11 Correct 1091 ms 28440 KB Output is correct
12 Correct 1081 ms 28408 KB Output is correct
13 Correct 1054 ms 28288 KB Output is correct
14 Correct 984 ms 28408 KB Output is correct
15 Correct 993 ms 28280 KB Output is correct
16 Correct 1054 ms 28408 KB Output is correct
17 Correct 963 ms 28408 KB Output is correct
18 Correct 947 ms 28408 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 27896 KB Output is correct
2 Correct 238 ms 28172 KB Output is correct
3 Correct 1642 ms 28280 KB Output is correct
4 Correct 1596 ms 28280 KB Output is correct
5 Correct 1551 ms 28280 KB Output is correct
6 Correct 1078 ms 28280 KB Output is correct
7 Correct 1276 ms 28408 KB Output is correct
8 Correct 1443 ms 28288 KB Output is correct
9 Correct 1555 ms 28308 KB Output is correct
10 Correct 1051 ms 28280 KB Output is correct
11 Correct 1091 ms 28440 KB Output is correct
12 Correct 1081 ms 28408 KB Output is correct
13 Correct 1054 ms 28288 KB Output is correct
14 Correct 984 ms 28408 KB Output is correct
15 Correct 993 ms 28280 KB Output is correct
16 Correct 1054 ms 28408 KB Output is correct
17 Correct 963 ms 28408 KB Output is correct
18 Correct 947 ms 28408 KB Output is correct
19 Correct 8029 ms 29752 KB Output is correct
20 Execution timed out 9057 ms 30200 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1528 ms 33140 KB Output is correct
2 Execution timed out 9087 ms 37616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 27896 KB Output is correct
2 Correct 238 ms 28172 KB Output is correct
3 Correct 1642 ms 28280 KB Output is correct
4 Correct 1596 ms 28280 KB Output is correct
5 Correct 1551 ms 28280 KB Output is correct
6 Correct 1078 ms 28280 KB Output is correct
7 Correct 1276 ms 28408 KB Output is correct
8 Correct 1443 ms 28288 KB Output is correct
9 Correct 1555 ms 28308 KB Output is correct
10 Correct 1051 ms 28280 KB Output is correct
11 Correct 1091 ms 28440 KB Output is correct
12 Correct 1081 ms 28408 KB Output is correct
13 Correct 1054 ms 28288 KB Output is correct
14 Correct 984 ms 28408 KB Output is correct
15 Correct 993 ms 28280 KB Output is correct
16 Correct 1054 ms 28408 KB Output is correct
17 Correct 963 ms 28408 KB Output is correct
18 Correct 947 ms 28408 KB Output is correct
19 Correct 8029 ms 29752 KB Output is correct
20 Execution timed out 9057 ms 30200 KB Time limit exceeded
21 Halted 0 ms 0 KB -