oj.uz

답안 #97817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97817 2019-02-18T16:23:01 Z scanhex Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 9000 ms 37468 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=300;
int sz2=300;

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);
		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]);
		}
		for(int j=0;j<300&&j<=i;++j){
			recalc(x[i-j]);
			answer[i]=max(answer[i],memos[x[i-j]]);
		}
	}
	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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 27944 KB Output is correct
2 Correct 304 ms 27996 KB Output is correct
3 Correct 787 ms 28280 KB Output is correct
4 Correct 760 ms 28272 KB Output is correct
5 Incorrect 786 ms 28276 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 27944 KB Output is correct
2 Correct 304 ms 27996 KB Output is correct
3 Correct 787 ms 28280 KB Output is correct
4 Correct 760 ms 28272 KB Output is correct
5 Incorrect 786 ms 28276 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 793 ms 33264 KB Output is correct
2 Execution timed out 9092 ms 37468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 27944 KB Output is correct
2 Correct 304 ms 27996 KB Output is correct
3 Correct 787 ms 28280 KB Output is correct
4 Correct 760 ms 28272 KB Output is correct
5 Incorrect 786 ms 28276 KB Output isn't correct
6 Halted 0 ms 0 KB -