Submission #588288

#	Time	Username	Problem	Language	Result	Execution time	Memory
588288		perchuts	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	22 ms	2820 KiB

bubblesort2

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
 
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e6+100;
 
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
 
int val[maxn], seg[4*maxn], lazy[4*maxn], as[maxn], vs[maxn], n, q;
ii freq[4*maxn];
 
vector<ii>v2 = {{-inf,0}};
 
//comprimir coordenadas de todos os valores (iniciais e alteracoes nas queries)
//necessario pra ordenar: max(0,posicao atual - posicao ordenada)
//pra achar posicao ordenada: seg de frequencia com compressao
//update: vou trocar x por y
//se x < y, todo mundo entre compressao(x) e compressao(y) diminui em 1.
//se x > y, todo mundo entre compressao(x) e compressao(y) aumenta em 1.
//se x=y, fodase
 
void updatef(int i,int l,int r,int x,int type){
    if(l>x||r<x)return;
    if(l==r){
        if(type==-inf)freq[i] = {0,-inf};
        else freq[i] = {1,type};
        return;
    }
    int md = (l+r)/2;
    updatef(2*i,l,md,x,type), updatef(2*i+1,md+1,r,x,type);
    freq[i].first = freq[2*i].first + freq[2*i+1].first, freq[i].second = max(freq[2*i].second,freq[2*i+1].second);
}
 
int query(int i,int l,int r,int x){
    if(l==r){
        return (freq[i].second<=x&&freq[i].first);
    }
    int md = (l+r)/2;
    if(freq[2*i].second<=x)return freq[2*i].first + query(2*i+1,md+1,r,x);
    return query(2*i,l,md,x);
}
 
void push(int i,int l,int r){
    seg[i] += lazy[i];
    if(l!=r)lazy[2*i] += lazy[i], lazy[2*i+1] += lazy[i];
    lazy[i] = 0;
}
 
void adiciona(int i,int l,int r,int x,int d){
    push(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        seg[i] = d;
        return;
    } 
    int md = (l+r)/2;
    adiciona(2*i,l,md,x,d), adiciona(2*i+1,md+1,r,x,d);
    seg[i] = max(seg[2*i],seg[2*i+1]);
}
 
 
void update(int i,int l,int r,int x,int y,int d){
    push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i] += d;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,y,d), update(2*i+1,md+1,r,x,y,d);
    seg[i] = max(seg[2*i],seg[2*i+1]);
}
 
 
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
	q=sz(x), n=sz(a);
 
    vector<int>answers;
 
    for(int i=1;i<=4*(n+q);++i)seg[i] = -6e5, freq[i] = {0,0};
 
    for(int i=0;i<n;++i){
        v2.pb({a[i],i+1});
    }
 
    for(int i=0;i<q;++i){
        v2.pb({v[i],n+1+i});
    }
 
    sort(all(v2));
 
    for(int i=1;i<=n+q;++i){
        if(v2[i].second<=n)as[v2[i].second-1] = v2[i].first, a[v2[i].second-1] = i;
        else vs[v2[i].second-1-n] = v2[i].first, v[v2[i].second-1-n] = i;
    }
 
    for(int i=0;i<n;++i){
        updatef(1,1,n+q,a[i],as[i]);
    }
    
    for(int i=0;i<n;++i){
        int precisa = max(0,i - query(1,1,n+q,as[i])+1);
        adiciona(1,1,n+q,a[i],precisa);
    }
 
    for(int i=0;i<q;++i){
        int atual = a[x[i]], novo = v[i];
 
        updatef(1,1,n+q,atual,-inf), adiciona(1,1,n+q,atual,-6e5), updatef(1,1,n+q,novo,vs[i]);
 
        int precisa = max(0,x[i] - query(1,1,n+q,vs[i])+1);
        
        if(atual<novo)update(1,1,n+q,atual,novo,1);
        if(atual>novo)update(1,1,n+q,novo,atual,-1);
 
        adiciona(1,1,n+q,novo,precisa);
 
        answers.pb(max(0,seg[1]));
        a[x[i]] = novo;
    }
    return answers;
}
 
//5 4 3 2 5
//4 3 2 5 5
//3 2 4 5 5
 
 
// int main(){
//     int n,q;cin>>n>>q;
//     vector<int>a;
//     for(int i=1;i<=n;++i){
//         int x;cin>>x;
//         a.pb(x);
//     }
//     vector<int>x,v;
//     for(int i=0;i<q;++i){
//         int d,f;cin>>d>>f;
//         x.pb(d), v.pb(f);
//     }
//     vector<int>resp = countScans(a,x,v);
//     for(auto x:resp)cout<<x<<" ";
// }

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