oj.uz

Submission #97801

# Submission time Handle Problem Language Result Execution time Memory
97801 2019-02-18T14:38:00 Z scanhex Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 67 ms 2040 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=100;
int sz2=0;

int memos[N];

void reb_int(){
}

int cnt=0;

void upd(int i,int coef){
	auto p=make_pair(a[i],i);
	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;
	}
	/*
	if(++cnt==1000){
		reb_int();
	}
	*/
}

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);
	copy(A.begin(),A.end(),a);
	for(int i=0;i<n;++i)upd(i,1);
	int q=x.size();
	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){
			answer[i]=max(answer[i],memos[j]);
		}
	}
	return answer;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -