oj.uz

Submission #205920

# Submission time Handle Problem Language Result Execution time Memory
205920 2020-03-01T10:35:24 Z GioChkhaidze Bubble Sort 2 (JOI18_bubblesort2) C++14
Compilation error
 0 ms 0 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=10003;
int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
vector < int > answer;  
vector < pair < pair < int , int > , bool > > s;
typedef struct { int x; int add; } res;
res v[8*N];

inline 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;
}

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);
}

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,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},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++) 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 (S<Yy || S<Xx) {
			for (int i=1; i<=q-i+1; i++)
			answer.push_back(1);
			return answer;
		}
 	
		if (Xx<=Yy) {
			idx=Xx,val=inf,Upd(1,1,S);
			L=Xx+1,R=Yy-1,dl=1;
			if (L<=R) Updlr(1,1,S);	
			idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);
		}
			else 
		if (Yy<=Xx) {
			idx=Xx,val=inf,Upd(1,1,S);
			L=Yy+1,R=Xx-1,dl=-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(v[1].x);
	}

	return answer;
}#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=10003;
int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
vector < int > answer;  
vector < pair < pair < int , int > , bool > > s;
typedef struct { int x; int add; } res;
res v[8*N];

inline 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;
}

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);
}

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,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},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++) 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 (S<Yy || S<Xx) {
			for (int i=1; i<=q-i+1; i++)
			answer.push_back(1);
			return answer;
		}
 	
		if (Xx<=Yy) {
			idx=Xx,val=inf,Upd(1,1,S);
			L=Xx+1,R=Yy-1,dl=1;
			if (L<=R) Updlr(1,1,S);	
			idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);
		}
			else 
		if (Yy<=Xx) {
			idx=Xx,val=inf,Upd(1,1,S);
			L=Yy+1,R=Xx-1,dl=-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(v[1].x);
	}

	return answer;
}

Compilation message

bubblesort2.cpp:95:2: error: stray '#' in program
 }#include <bits/stdc++.h>
  ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) 
                ~^~~~~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:95:3: error: 'include' does not name a type
 }#include <bits/stdc++.h>
   ^~~~~~~
bubblesort2.cpp:103:11: error: redefinition of 'const int N'
 const int N=10003;
           ^
bubblesort2.cpp:9:11: note: 'const int N' previously defined here
 const int N=10003;
           ^
bubblesort2.cpp:104:5: error: redefinition of 'int n'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
     ^
bubblesort2.cpp:10:5: note: 'int n' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
     ^
bubblesort2.cpp:104:7: error: redefinition of 'int q'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
       ^
bubblesort2.cpp:10:7: note: 'int q' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
       ^
bubblesort2.cpp:101:11: error: redefinition of 'int second'
 #define S second
           ^
bubblesort2.cpp:104:9: note: in expansion of macro 'S'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
         ^
bubblesort2.cpp:7:11: note: 'int second' previously declared here
 #define S second
           ^
bubblesort2.cpp:10:9: note: in expansion of macro 'S'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
         ^
bubblesort2.cpp:104:11: error: redefinition of 'int L'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
           ^
bubblesort2.cpp:10:11: note: 'int L' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
           ^
bubblesort2.cpp:104:13: error: redefinition of 'int R'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
             ^
bubblesort2.cpp:10:13: note: 'int R' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
             ^
bubblesort2.cpp:104:15: error: redefinition of 'int dl'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
               ^~
bubblesort2.cpp:10:15: note: 'int dl' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
               ^~
bubblesort2.cpp:104:18: error: redefinition of 'int idx'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                  ^~~
bubblesort2.cpp:10:18: note: 'int idx' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                  ^~~
bubblesort2.cpp:104:22: error: redefinition of 'int val'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                      ^~~
bubblesort2.cpp:10:22: note: 'int val' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                      ^~~
bubblesort2.cpp:104:26: error: redefinition of 'int Xx'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                          ^~
bubblesort2.cpp:10:26: note: 'int Xx' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                          ^~
bubblesort2.cpp:104:29: error: redefinition of 'int Yy'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                             ^~
bubblesort2.cpp:10:29: note: 'int Yy' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                             ^~
bubblesort2.cpp:104:35: error: redefinition of 'int a [10003]'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                   ^
bubblesort2.cpp:10:32: note: 'int a [10003]' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                ^
bubblesort2.cpp:104:42: error: redefinition of 'int pos [10003]'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                          ^
bubblesort2.cpp:10:37: note: 'int pos [10003]' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                     ^~~
bubblesort2.cpp:104:47: error: redefinition of 'int x [10003]'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                               ^
bubblesort2.cpp:10:44: note: 'int x [10003]' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                            ^
bubblesort2.cpp:104:54: error: redefinition of 'int G [20006]'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                                      ^
bubblesort2.cpp:10:49: note: 'int G [20006]' previously declared here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                                 ^
bubblesort2.cpp:104:56: error: redefinition of 'int inf'
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                                        ^~~
bubblesort2.cpp:10:56: note: 'int inf' previously defined here
 int n,q,S,L,R,dl,idx,val,Xx,Yy,a[N],pos[N],x[N],G[2*N],inf=-1e9;
                                                        ^~~
bubblesort2.cpp:105:16: error: redefinition of 'std::vector<int> answer'
 vector < int > answer;  
                ^~~~~~
bubblesort2.cpp:11:16: note: 'std::vector<int> answer' previously declared here
 vector < int > answer;  
                ^~~~~~
bubblesort2.cpp:106:47: error: redefinition of 'std::vector<std::pair<std::pair<int, int>, bool> > s'
 vector < pair < pair < int , int > , bool > > s;
                                               ^
bubblesort2.cpp:12:47: note: 'std::vector<std::pair<std::pair<int, int>, bool> > s' previously declared here
 vector < pair < pair < int , int > , bool > > s;
                                               ^
bubblesort2.cpp:107:36: error: conflicting declaration 'typedef struct res res'
 typedef struct { int x; int add; } res;
                                    ^~~
bubblesort2.cpp:13:36: note: previous declaration as 'typedef struct res res'
 typedef struct { int x; int add; } res;
                                    ^~~
bubblesort2.cpp:108:10: error: redefinition of 'res v [80024]'
 res v[8*N];
          ^
bubblesort2.cpp:14:5: note: 'res v [80024]' previously declared here
 res v[8*N];
     ^
bubblesort2.cpp: In function 'void Shift(int, int, int)':
bubblesort2.cpp:110:13: error: redefinition of 'void Shift(int, int, int)'
 inline void Shift(Tree) {
             ^~~~~
bubblesort2.cpp:16:13: note: 'void Shift(int, int, int)' previously defined here
 inline void Shift(Tree) {
             ^~~~~
bubblesort2.cpp: In function 'void Updlr(int, int, int)':
bubblesort2.cpp:120:6: error: redefinition of 'void Updlr(int, int, int)'
 void Updlr(Tree) {
      ^~~~~
bubblesort2.cpp:26:6: note: 'void Updlr(int, int, int)' previously defined here
 void Updlr(Tree) {
      ^~~~~
bubblesort2.cpp: In function 'void Upd(int, int, int)':
bubblesort2.cpp:128:6: error: redefinition of 'void Upd(int, int, int)'
 void Upd(Tree) {
      ^~~
bubblesort2.cpp:34:6: note: 'void Upd(int, int, int)' previously defined here
 void Upd(Tree) {
      ^~~
bubblesort2.cpp: In function 'void Up(int, int)':
bubblesort2.cpp:136:6: error: redefinition of 'void Up(int, int)'
 void Up(int x,int dl) { while (x<=S) { G[x]+=dl; x+=(x & -x); } }
      ^~
bubblesort2.cpp:42:6: note: 'void Up(int, int)' previously defined here
 void Up(int x,int dl) { while (x<=S) { G[x]+=dl; x+=(x & -x); } }
      ^~
bubblesort2.cpp: In function 'int Ge(int)':
bubblesort2.cpp:137:5: error: redefinition of 'int Ge(int)'
 int Ge(int x) { int Res=0; while (x>0) { Res+=G[x]; x-=(x & -x); } return Res; }
     ^~
bubblesort2.cpp:43:5: note: 'int Ge(int)' previously defined here
 int Ge(int x) { int Res=0; while (x>0) { Res+=G[x]; x-=(x & -x); } return Res; }
     ^~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:139:18: error: redefinition of 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)'
 std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
                  ^~~~~~~~~~
bubblesort2.cpp:45:18: note: 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
 std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
                  ^~~~~~~~~~
bubblesort2.cpp:149:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) 
                ~^~~~~~~~~