oj.uz

답안 #206430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206430 2020-03-03T09:38:19 Z GioChkhaidze Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 23 ms 2544 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 F first
#define S second
using namespace std;
const int N=5e5+5;
int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[4*N],inf=-1e9;
vector < int > answer;  
vector < pair < pair < int , int > , pair < bool , int >  > > s;
typedef struct { int x; int add; } res;
res v[8*N];

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

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

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

void Up(int x,int dl) { 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},{1,i}});
	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]},{0,i}});
	
	sort(s.begin(),s.end()),S=s.size();
	
	for (int i=0; i<S; i++) 
		if (s[i].S.F) a[s[i].S.S]=i+1;
			else x[s[i].S.S]=i+1;
		
	for (int i=1; i<=n; i++) Up(a[i],1);
	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);

	for (int i=1; i<=q; i++) {	
		Xx=a[pos[i]],Yy=x[i];
		Up(a[pos[i]],-1),Up(x[i],1);
 	
 		if (Xx<=Yy) dl=1; else dl=-1;
 	
 		idx=Xx,val=inf,Upd(1,1,S);
		L=min(Xx,Yy)+1,R=max(Xx,Yy)-1;
		if (L<=R) Updlr(1,1,S);	
		idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);

		a[pos[i]]=x[i];
		answer.push_back(max(v[1].x,0));
	}

	return answer;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 8 ms 760 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 9 ms 760 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 8 ms 760 KB Output is correct
8 Correct 9 ms 888 KB Output is correct
9 Correct 8 ms 760 KB Output is correct
10 Correct 8 ms 764 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 8 ms 760 KB Output is correct
13 Correct 9 ms 760 KB Output is correct
14 Correct 10 ms 840 KB Output is correct
15 Correct 8 ms 760 KB Output is correct
16 Correct 9 ms 760 KB Output is correct
17 Correct 8 ms 760 KB Output is correct
18 Correct 8 ms 760 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 8 ms 760 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 9 ms 760 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 8 ms 760 KB Output is correct
8 Correct 9 ms 888 KB Output is correct
9 Correct 8 ms 760 KB Output is correct
10 Correct 8 ms 764 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 8 ms 760 KB Output is correct
13 Correct 9 ms 760 KB Output is correct
14 Correct 10 ms 840 KB Output is correct
15 Correct 8 ms 760 KB Output is correct
16 Correct 9 ms 760 KB Output is correct
17 Correct 8 ms 760 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 19 ms 1780 KB Output is correct
20 Correct 21 ms 1780 KB Output is correct
21 Correct 21 ms 1784 KB Output is correct
22 Correct 21 ms 1780 KB Output is correct
23 Correct 20 ms 1780 KB Output is correct
24 Correct 20 ms 1780 KB Output is correct
25 Correct 21 ms 1908 KB Output is correct
26 Correct 20 ms 1780 KB Output is correct
27 Correct 19 ms 1780 KB Output is correct
28 Correct 19 ms 1780 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 8 ms 760 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 9 ms 760 KB Output is correct
6 Correct 8 ms 760 KB Output is correct
7 Correct 8 ms 760 KB Output is correct
8 Correct 9 ms 888 KB Output is correct
9 Correct 8 ms 760 KB Output is correct
10 Correct 8 ms 764 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 8 ms 760 KB Output is correct
13 Correct 9 ms 760 KB Output is correct
14 Correct 10 ms 840 KB Output is correct
15 Correct 8 ms 760 KB Output is correct
16 Correct 9 ms 760 KB Output is correct
17 Correct 8 ms 760 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 19 ms 1780 KB Output is correct
20 Correct 21 ms 1780 KB Output is correct
21 Correct 21 ms 1784 KB Output is correct
22 Correct 21 ms 1780 KB Output is correct
23 Correct 20 ms 1780 KB Output is correct
24 Correct 20 ms 1780 KB Output is correct
25 Correct 21 ms 1908 KB Output is correct
26 Correct 20 ms 1780 KB Output is correct
27 Correct 19 ms 1780 KB Output is correct
28 Correct 19 ms 1780 KB Output is correct
29 Incorrect 23 ms 2544 KB Output isn't correct
30 Halted 0 ms 0 KB -