Submission #77712

#	Time	Username	Problem	Language	Result	Execution time	Memory
77712		nxteru	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	6476 ms	493756 KiB

bubblesort2

#include "bubblesort2.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000
int n,q,seg[1<<21],la[1<<21],x[500005],p[500005],v[500005];
priority_queue<int>d[1000005];
set<int>u[1000005];
vector<int>cm;
map<int,int>pr;
void lazy(int l,int r,int k){
	seg[k]+=la[k];
	if(l!=r){
		la[k*2+1]+=la[k];
		la[k*2+2]+=la[k];
	}
	la[k]=0;
}
void add(int a,int b,int l,int r,int k,int x){
	lazy(l,r,k);
	if(r<a||b<l)return;
	if(a<=l&&r<=b){
		la[k]+=x;
		lazy(l,r,k);
		return;
	}
	add(a,b,l,(l+r-1)/2,k*2+1,x);
	add(a,b,(l+r+1)/2,r,k*2+2,x);
	seg[k]=max(seg[k*2+1],seg[k*2+2]);
}
int que(int a,int b,int l,int r,int k){
	lazy(l,r,k);
	if(r<a||b<l)return -INF;
	if(a<=l&&r<=b)return seg[k];
	return max(que(a,b,l,(l+r-1)/2,k*2+1),que(a,b,(l+r+1)/2,r,k*2+2));
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	vector<int>ans;
	n=A.size();
	q=X.size();
	for(int i=0;i<n;i++){
		x[i]=A[i];
		cm.PB(x[i]);
	}
	for(int i=0;i<q;i++){
		p[i]=X[i];
		v[i]=V[i];
		cm.PB(v[i]);
	}
	sort(cm.begin(),cm.end());
	cm.erase(unique(cm.begin(),cm.end()),cm.end());
	for(int i=0;i<cm.size();i++)pr[cm[i]]=i;
	for(int i=0;i<n;i++)x[i]=pr[x[i]];
	for(int i=0;i<q;i++)v[i]=pr[v[i]];
	for(int i=0;i<cm.size();i++){
		d[i].push(0);
		u[i].insert(0);
	}
	for(int i=0;i<n;i++){
		add(x[i],cm.size()-1,0,(1<<20)-1,0,-1);
		d[x[i]].push(i+1);
		u[x[i]].insert(i+1);
	}
	for(int i=0;i<cm.size();i++){
		add(i,i,0,(1<<20)-1,0,d[i].top());
	}
	for(int i=0;i<q;i++){
		int a=p[i],b=v[i];
		if(x[a]==b){
			ans.PB(que(0,cm.size(),0,(1<<20)-1,0));
			continue;
		}
		add(x[a],cm.size()-1,0,(1<<20)-1,0,1);
		add(b,cm.size()-1,0,(1<<20)-1,0,-1);
		u[x[a]].erase(a+1);
		if(d[x[a]].top()==a+1){
			while(u[x[a]].find(d[x[a]].top())==u[x[a]].end())d[x[a]].pop();
			add(x[a],x[a],0,(1<<20)-1,0,-(a+1)+d[x[a]].top());
		}
		x[a]=b;
		u[b].insert(a+1);
		if(d[b].top()<a+1){
			add(b,b,0,(1<<20)-1,0,-d[b].top()+a+1);
		}
		d[b].push(a+1);
		ans.PB(que(0,cm.size(),0,(1<<20)-1,0));
	}
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cm.size();i++)pr[cm[i]]=i;
              ~^~~~~~~~~~
bubblesort2.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cm.size();i++){
              ~^~~~~~~~~~
bubblesort2.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cm.size();i++){
              ~^~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40