Submission #277953

#	Time	Username	Problem	Language	Result	Execution time	Memory
277953		Revo7	Bubble Sort 2 (JOI18_bubblesort2)	C++14	60 / 100	945 ms	11156 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
#define pb push_back

using namespace std;

vector<int> countScans(vector<int> a,vector<int> pos,vector<int> v){
    if(a.size()<=8000){
         set<pair<int,int>>s;
    for(int i=0;i<a.size();i++){
        s.insert({a[i],i});
    }
    vector<int>ans;
    for(int i=0;i<pos.size();i++){
        int mx=0;
        s.erase({a[pos[i]],pos[i]});
        a[pos[i]]=v[i];
        s.insert({a[pos[i]],pos[i]});
        int cur=0;
        for(auto x:s){
            mx=max(mx,x.second-cur);
            cur++;
        }
        ans.pb(mx);
        //cout<<ans.back()<<endl;
    }
	return ans;
    }
    set<int>s[111];

    for(int i=0;i<a.size();i++){
        s[a[i]].insert(i);
    }
    vector<int>ans;

    for(int i=0;i<pos.size();i++){
        //cout<<i<<endl;
        int mx=0,id=pos[i],newval=v[i];
        s[a[id]].erase(id);
        a[id]=newval;
        s[newval].insert(id);
        int cur=0;
        for(int j=1;j<=100;j++){
            cur+=s[j].size();
            if(s[j].size())
            mx=max(mx,*s[j].rbegin()-cur+1);
        }
        ans.pb(mx);
    }
	return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
bubblesort2.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<pos.size();i++){
      |                 ~^~~~~~~~~~~
bubblesort2.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
bubblesort2.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<pos.size();i++){
      |                 ~^~~~~~~~~~~

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