oj.uz

Submission #19114

# Submission time Handle Problem Language Result Execution time Memory
19114 2016-02-18T13:34:53 Z mindol 버블 정렬 (OJUZ10_bubblesort) C++14
100 / 100
 216 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;
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 3 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 2 ms 4044 KB Output is correct
5 Correct 0 ms 4044 KB Output is correct
6 Correct 2 ms 4044 KB Output is correct
7 Correct 0 ms 4044 KB Output is correct
8 Correct 1 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 184 ms 6100 KB Output is correct
2 Correct 216 ms 6100 KB Output is correct
3 Correct 184 ms 6100 KB Output is correct
4 Correct 152 ms 6100 KB Output is correct
5 Correct 176 ms 6100 KB Output is correct
6 Correct 209 ms 6100 KB Output is correct
7 Correct 200 ms 6100 KB Output is correct
8 Correct 208 ms 6100 KB Output is correct
9 Correct 170 ms 6100 KB Output is correct
10 Correct 185 ms 6100 KB Output is correct
11 Correct 134 ms 6100 KB Output is correct
12 Correct 202 ms 6100 KB Output is correct
13 Correct 61 ms 5076 KB Output is correct
14 Correct 200 ms 6100 KB Output is correct
15 Correct 180 ms 6100 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 6100 KB Output is correct
2 Correct 162 ms 6100 KB Output is correct
3 Correct 184 ms 6100 KB Output is correct
4 Correct 203 ms 6100 KB Output is correct
5 Correct 202 ms 6100 KB Output is correct
6 Correct 200 ms 6100 KB Output is correct
7 Correct 73 ms 5076 KB Output is correct
8 Correct 137 ms 6100 KB Output is correct
9 Correct 190 ms 6100 KB Output is correct
10 Correct 203 ms 6100 KB Output is correct
11 Correct 207 ms 6100 KB Output is correct
12 Correct 191 ms 6100 KB Output is correct
13 Correct 193 ms 6100 KB Output is correct
14 Correct 205 ms 6100 KB Output is correct
15 Correct 185 ms 6100 KB Output is correct