oj.uz

Submission #772070

# Submission time Handle Problem Language Result Execution time Memory
772070 2023-07-03T15:15:41 Z HoriaHaivas San (COCI17_san) C++14
120 / 120
 219 ms 21072 KB 
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct cladire
{
    int h;
    int g;
    int poz;
};

struct subsirhigh
{
    int sum;
    int highest;
};

struct subsirlow
{
    int sum;
    int lowest;
};

cladire building[42];
int aib[42]; /// praise the data structure
///count the inversions
vector<subsirhigh> firsthalf;
vector<subsirlow> secondhalf;
int n,k,i,j,val,ans,r,pas,ree,calculated;

bool cmp (cladire a, cladire b)
{
    return a.h<b.h;
}

bool cmp2(subsirhigh a, subsirhigh b)
{
    return a.sum<b.sum;
}

bool cmp3(cladire a, cladire b)
{
    return a.poz<b.poz;
}

bool cmp4(subsirlow a, subsirlow b)
{
    return a.sum<b.sum;
}

void gen(int r)
{
    int mask,currsum,currhighest,j;
    bool ok;
    for (mask=1; mask<(1<<r); mask++)
    {
        ok=true;
        currsum=0;
        currhighest=-1;
        for (j=0; j<r && ok; j++)
        {
            if (mask&(1<<j))
            {
                if (building[j+1].h>=currhighest)
                {
                    currsum+=building[j+1].g;
                    currhighest=building[j+1].h;
                }
                else
                {
                    ok=false;
                }
            }
        }
        if (ok)
        {
            if (currsum>=k)
                ans++;
            firsthalf.push_back({currsum,currhighest});
        }
    }
}

void gen2(int r)
{
    int mask,j,currsum,currhighest,currlowest;
    bool ok;
    for (mask=1; mask<(1<<r); mask++)
    {
        ok=true;
        currsum=0;
        currhighest=0;
        currlowest=n+1;
        for (j=0; j<r && ok; j++)
        {
            if (mask&(1<<j))
            {
                if (building[j+n/2+1].h>=currhighest)
                {
                    currsum+=building[j+n/2+1].g;
                    currhighest=building[j+n/2+1].h;
                    currlowest=min(currlowest,building[j+n/2+1].h);
                }
                else
                {
                    ok=false;
                }
            }
        }
        if (ok)
        {
            if (currsum>=k)
                ans++;
            secondhalf.push_back({currsum,currlowest});
        }
    }
}

void update(int index, int delta)
{
    while (index<=n)
    {
        aib[index]+=delta;
        index+=index&(-index);
    }
}

int query(int index)
{
    int s;
    s=0;
    while (index>0)
    {
         s+=aib[index];
         index-=index&(-index);
    }
    return s;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (i=1; i<=n; i++)
    {
        cin >> building[i].h >> building[i].g;
        building[i].poz=i;
    }
    sort(building+1,building+1+n,cmp);
    val=0;
    for (i=1; i<=n; i++)
    {
        if (i==1 || building[i].h!=building[i-1].h)
            val++;
        building[i].h=val;
    }
    sort(building+1,building+1+n,cmp3);
    ans=0;
    gen(n/2);
    sort(firsthalf.begin(),firsthalf.end(),cmp2);
    if (n%2==1)
    gen2(n/2+1);
    else
    gen2(n/2);
    sort(secondhalf.begin(),secondhalf.end(),cmp4);
    calculated=firsthalf.size()-1;
    for (i=0;i<secondhalf.size();i++)
    {
         r=0;
         pas=(1<<20);
         while (pas)
         {
              if (r+pas<firsthalf.size() && secondhalf[i].sum+firsthalf[r+pas].sum<k)
                  r+=pas;
              pas=pas/2;
         }
         if(secondhalf[i].sum+firsthalf[r].sum<k)
            r++;
         if (r!=firsthalf.size())
         {
            while (calculated>=r)
            {
                   update(firsthalf[calculated].highest,1);
                   calculated--;
            }
            ans+=query(secondhalf[i].lowest);
         }
    }
    cout << ans;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:177:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsirlow>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (i=0;i<secondhalf.size();i++)
      |              ~^~~~~~~~~~~~~~~~~~
san.cpp:183:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsirhigh>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |               if (r+pas<firsthalf.size() && secondhalf[i].sum+firsthalf[r+pas].sum<k)
      |                   ~~~~~^~~~~~~~~~~~~~~~~
san.cpp:189:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsirhigh>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |          if (r!=firsthalf.size())
      |              ~^~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1992 KB Output is correct
2 Correct 3 ms 468 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5216 KB Output is correct
2 Correct 14 ms 996 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 21072 KB Output is correct
2 Correct 86 ms 3508 KB Output is correct