oj.uz

답안 #205779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205779 2020-02-29T21:06:23 Z GioChkhaidze Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 23 ms 3444 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define F first
#define S second
using namespace std;
const int N=5e5+5;

long long inf=-100000000000000000LL;
int n,q,S;
int a[N],pos[N],x[N];
int G[2*N];

map < int , int > f;
vector < int > answer;  
vector < pair < pair < int , int > , bool > > s;
typedef struct { ll x; int add; } res;
res v[4*N];

void Shift(Tree) {
	if (!v[h].add) return ;
	v[h].x+=v[h].add;
	if (l!=r) {
		v[(h<<1)].add+=v[h].add;
		v[((h<<1)|1)].add+=v[h].add;
	}
	v[h].add=0;
}

int L,R,dl;
void Updlr(Tree) {
	Shift(h,l,r);
	if (R<l || r<L) return ;
	if (L<=l && r<=R) {
		v[h].add+=dl;
		Shift(h,l,r);
		return ;
	}
	Updlr(Left),Updlr(Right);
	v[h].x=max(v[(h<<1)].x,v[((h<<1)|1)].x);
}

int idx;
ll val;
void Upd(Tree) {
	Shift(h,l,r);
	if (r<idx || idx<l) return ;
	if (l==idx && r==idx) { v[h].x=val; return ; }
	Upd(Left),Upd(Right);
	v[h].x=max(v[(h<<1)].x,v[((h<<1)|1)].x);
}

void Up(int x) {
	while (x<=S) {
		G[x]+=dl;
		x+=(x & -x);
	}
}

int Ge(int x) {
	int res=0;
	while (x>0) {
		res+=G[x];
		x-=(x & -x);
	}
	return res;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	n=A.size(),q=X.size();
	
	for (int i=1; i<=n; i++) {
		a[i]=A[i-1];
		s.push_back({{a[i],n-i},0});
	}
	
	for (int i=1; i<=q; i++) {
		pos[i]=X[i-1]+1,x[i]=V[i-1];
		s.push_back({{x[i],n-pos[i]},1});
	}
	
	sort(s.begin(),s.end());
	S=s.size();
	
	for (int i=0; i<s.size(); i++) 
		if (!s[i].S) 
			a[-(s[i].F.S-n)]=i+1;
				else
			x[-(s[i].F.S-n)]=i+1;
		
	for (int i=1; i<=n; i++) dl=1,Up(a[i]);
	for (int i=1; i<=4*S; i++) v[i].x=inf;
	
	for (int i=1; i<=n; i++) {
		idx=a[i],val=i-Ge(a[i]);	
		Upd(1,1,S);
	}	
	
	int Xx,Yy;
	for (int i=1; i<=q; i++) {
		Xx=a[pos[i]],Yy=x[i];
		
		dl=-1,Up(a[pos[i]]);
		dl=1,Up(x[i]);
		
		if (Xx<=Yy) {
			idx=Xx,val=inf,Upd(1,1,S);
			L=Xx+1,R=Yy-1,dl=1,Updlr(1,1,S);
			idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);
		}
			else {
			idx=Xx,val=inf,Upd(1,1,S);
			L=Yy+1,R=Xx-1,dl=-1,Updlr(1,1,S);
			idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);
		}
		
		a[pos[i]]=x[i];
		answer.push_back(v[1].x);
	}

	return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) 
                ~^~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 3444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 8 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -