oj.uz

Submission #200573

# Submission time Handle Problem Language Result Execution time Memory
200573 2020-02-07T12:01:24 Z mamadmokhi Kisik (COCI19_kisik) C++17
90 / 90
 1242 ms 54660 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=1e18;
       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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 245 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 16664 KB Output is correct
2 Correct 767 ms 36220 KB Output is correct
3 Correct 741 ms 35380 KB Output is correct
4 Correct 700 ms 32408 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 24084 KB Output is correct
2 Correct 73 ms 5840 KB Output is correct
3 Correct 152 ms 10700 KB Output is correct
4 Correct 569 ms 28764 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 14016 KB Output is correct
2 Correct 597 ms 31740 KB Output is correct
3 Correct 427 ms 23076 KB Output is correct
4 Correct 1242 ms 54660 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 17584 KB Output is correct
2 Correct 1146 ms 50824 KB Output is correct
3 Correct 299 ms 17072 KB Output is correct
4 Correct 825 ms 39164 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 36652 KB Output is correct
2 Correct 743 ms 35468 KB Output is correct
3 Correct 582 ms 28324 KB Output is correct
4 Correct 349 ms 19628 KB Output is correct