oj.uz

Submission #19113

# Submission time Handle Problem Language Result Execution time Memory
19113 2016-02-18T13:31:06 Z mindol 버블 정렬 (OJUZ10_bubblesort) C++14
100 / 100
 210 ms 6100 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

struct segtree
{
    int tree[1<<18],base=1<<17;
    void add(int place)
    {
        for(place+=base-1;place>=1;place>>=1)
            tree[place]++;
    }
    int rangeSum(int s,int e)
    {
        int sum=0;
        for(s+=base-1,e+=base-1;s<=e;s>>=1,e>>=1)
        {
            if(s&1) sum+=tree[s++];
            if(!(e&1)) sum+=tree[e--];
        }
        return sum;
    }
} p,q;

vector<int> cpr,z;
vector<pair<int,int>> v;
int a[100001];
int fin[100001];

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cpr.push_back(a[i]);
    }
    sort(cpr.begin(),cpr.end());
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(cpr.begin(),cpr.end(),a[i])-cpr.begin()+1;
        p.add(a[i]);

        int c=p.rangeSum(a[i]+1,n);
        if(k<=c) c=i-k;
        else c=i-c;
        v.push_back(make_pair(a[i],c));
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
    {
        int s=v[i].second,e=n,ans;
        while(s<=e)
        {
            int mid=(s+e)/2;
            int res=q.rangeSum(s,mid);
            if(res<mid-s+1)
                ans=mid, e=mid-1;
            else s=mid+1;
        }
        q.add(ans);
        fin[ans]=v[i].first;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",cpr[fin[i]-1]);
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4044 KB Output is correct
2 Correct 0 ms 4044 KB Output is correct
3 Correct 0 ms 4044 KB Output is correct
4 Correct 0 ms 4044 KB Output is correct
5 Correct 0 ms 4044 KB Output is correct
6 Correct 0 ms 4044 KB Output is correct
7 Correct 0 ms 4044 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4044 KB Output is correct
2 Correct 0 ms 4044 KB Output is correct
3 Correct 0 ms 4044 KB Output is correct
4 Correct 0 ms 4044 KB Output is correct
5 Correct 2 ms 4044 KB Output is correct
6 Correct 0 ms 4044 KB Output is correct
7 Correct 2 ms 4044 KB Output is correct
8 Correct 0 ms 4044 KB Output is correct
9 Correct 2 ms 4044 KB Output is correct
10 Correct 3 ms 4044 KB Output is correct

Subtask #3
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 6100 KB Output is correct
2 Correct 191 ms 6100 KB Output is correct
3 Correct 190 ms 6100 KB Output is correct
4 Correct 151 ms 6100 KB Output is correct
5 Correct 200 ms 6100 KB Output is correct
6 Correct 128 ms 6100 KB Output is correct
7 Correct 203 ms 6100 KB Output is correct
8 Correct 202 ms 6100 KB Output is correct
9 Correct 205 ms 6100 KB Output is correct
10 Correct 201 ms 6100 KB Output is correct
11 Correct 183 ms 6100 KB Output is correct
12 Correct 204 ms 6100 KB Output is correct
13 Correct 169 ms 6100 KB Output is correct
14 Correct 63 ms 5076 KB Output is correct
15 Correct 178 ms 6100 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 6100 KB Output is correct
2 Correct 183 ms 6100 KB Output is correct
3 Correct 185 ms 6100 KB Output is correct
4 Correct 198 ms 6100 KB Output is correct
5 Correct 137 ms 6100 KB Output is correct
6 Correct 64 ms 5076 KB Output is correct
7 Correct 210 ms 6100 KB Output is correct
8 Correct 189 ms 6100 KB Output is correct
9 Correct 197 ms 6100 KB Output is correct
10 Correct 157 ms 6100 KB Output is correct
11 Correct 203 ms 6100 KB Output is correct
12 Correct 181 ms 6100 KB Output is correct
13 Correct 209 ms 6100 KB Output is correct
14 Correct 200 ms 6100 KB Output is correct
15 Correct 170 ms 6100 KB Output is correct