oj.uz

답안 #200572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200572 2020-02-07T11:41:43 Z mamadmokhi Kisik (COCI19_kisik) C++17
0 / 90
 1193 ms 38280 KB 
     // give up :((((
    #include <bits/stdc++.h>
    #define mp make_pair
    #define f1 first
    #define f2 second
    #define pb push_back
    #define int long long
    #define pii pair<int ,int>
    #define ios  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    using namespace std;
    const int mox=1e6+9;
    vector<pii> ha,wa;
    int ko[mox];
    int tree[mox][2];
    int n;
    void add(int id , int x ,int z)
    {
        for(int i=id ; i<=n ; i+=(i&(-i)))
        {
            tree[i][z]+=x;
        }
    }
    int get(int id , int z)
    {    int ans=0;
        for(int i=id ; i>0 ; i-=(i&(-i)))
        {
            ans+=tree[i][z];
        }
        return ans;
    }
    int32_t main()
    {

        int k;
       cin>>n>>k;
       for(int i=0 ; i<n ; i++)
       {
           int a,b;
           cin>>b>>a;
           ha.pb({a,i});
           wa.pb({b,i});
       }
       sort(ha.begin(),ha.end());
       sort(wa.begin(),wa.end());
       int ans=1e12;
       for(int i=0 ; i<n ; i++)
       {
           ko[wa[i].f2]=i;
       }
       for(int i=0 ; i<n ; i++)
       {
           add(ko[ha[i].f2]+1,wa[ko[ha[i].f2]].f1,0);
           add(ko[ha[i].f2]+1,1,1);
           int low=0;
           int hi=n+1;
           while(low<hi-1)
           {
               int mid=(low+hi)/2;
               if(get(mid,1)>=k)
               {
                   hi=mid;
               }
               else
                low=mid;
           }
           if(hi!=n+1)
           {
               ans=min(ans,get(hi,0)*ha[i].f1);
           }
       }
       cout<<ans<<'\n';

    }

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 483 ms 18480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 762 ms 25596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 429 ms 15688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 538 ms 19376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1193 ms 38280 KB Output isn't correct
2 Halted 0 ms 0 KB -