oj.uz

Submission #200567

# Submission time Handle Problem Language Result Execution time Memory
200567 2020-02-07T11:27:31 Z mamadmokhi Kisik (COCI19_kisik) C++17
0 / 90
 783 ms 45436 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()
    {
           ios
        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;

    }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 20784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 491 ms 29488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 17216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 353 ms 21680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 783 ms 45436 KB Output isn't correct
2 Halted 0 ms 0 KB -