oj.uz

답안 #367899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367899 2021-02-18T18:56:47 Z denkendoemeer Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 9 ms 1772 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
using namespace std;
int offset[100005],f[100005],val[100005],aint[1000005],lazy[1000005];
vector<int>aux;
int n,q,l;
void push(int nod,int st,int dr)
{
    if (lazy[nod]){
        aint[nod]+=lazy[nod];
        if (st!=dr){
            lazy[nod*2]+=lazy[nod];
            lazy[nod*2+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
}
void update(int nod,int st,int dr,int l,int r,int add)
{
    if (l>r)
        return ;
    if (l<=st && dr<=r){
        aint[nod]+=add;
        if (st!=dr){
            lazy[nod*2]+=add;
            lazy[nod*2+1]+=add;
        }
        return ;
    }
    push(nod,st,dr);
    int mij=(st+dr)/2;
    if (l<=mij)
        update(nod*2,st,mij,l,r,add);
    if (mij+1<=r)
        update(nod*2+1,mij+1,dr,l,r,add);
    push(nod*2,st,mij);
    push(nod*2+1,mij+1,dr);
    aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
void update2(int nod,int st,int dr,int poz,int val)
{
    assert(st<=dr && st<=poz && poz<=dr);
    assert(nod<=4000000);
    if (st==dr){
        aint[nod]+=val;
        return ;
    }
    //push(nod,st,dr);
    int mij=(st+dr)/2;
    if (poz<=mij)
        update2(nod*2,st,mij,poz,val);
    else
        update2(nod*2+1,mij+1,dr,poz,val);
    //push(nod*2,st,mij);
    //push(nod*2+1,mij+1,dr);
    aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
int add(int poz,int nr)
{
    if (val[poz]!=2e9){
        //update(1,0,l-1,val[poz]+1,l-1,1);
        assert(val[poz]<=l-1);
        update2(1,0,l-1,val[poz],-poz);
    }
    val[poz]=nr;
    //update(1,0,l-1,val[poz]+1,l-1,-1);
    assert(val[poz]<=l-1);
    update2(1,0,l-1,val[poz],poz);
}
vector<int> countScans(vector<int>a,vector<int>x,vector<int>v)
{
    n=a.size();
    q=x.size();
    int i;
    for(i=0;i<n;i++)
        aux.push_back(a[i]);
    for(i=0;i<q;i++)
        aux.push_back(v[i]);
    sort(aux.begin(),aux.end());
    aux.resize(unique(aux.begin(),aux.end())-aux.begin());
    for(i=0;i<n;i++)
        a[i]=lower_bound(aux.begin(),aux.end(),a[i])-aux.begin();
    for(i=0;i<q;i++)
        v[i]=lower_bound(aux.begin(),aux.end(),v[i])-aux.begin();
    l=n+q;
    for(i=0;i<n;i++)
        offset[a[i]+1]++;
    for(i=0;i<q;i++)
        offset[v[i]+1]++;
    for(i=2;i<aux.size();i++)
        offset[i]=offset[i-1]+offset[i];
    for(i=0;i<n;i++)
        val[i]=2e9;
    vector<int>ans;
    for(i=0;i<n;i++)
        add(i,offset[a[i]]+f[a[i]]),f[a[i]]++;
    /*for(i=0;i<q;i++){
        add(x[i],offset[v[i]]+f[v[i]]),f[v[i]]++;
        ans.push_back(aint[1]);
    }*/
    return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(i=2;i<aux.size();i++)
      |             ~^~~~~~~~~~~
bubblesort2.cpp: In function 'int add(int, int)':
bubblesort2.cpp:69:12: warning: control reaches end of non-void function [-Wreturn-type]
   69 |     update2(1,0,l-1,val[poz],poz);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 1772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -