Submission #200573

#	Time	Username	Problem	Language	Result	Execution time	Memory
200573		mamadmokhi	Kisik (COCI19_kisik)	C++17	90 / 90	1242 ms	54660 KiB

kisik

     // 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10