oj.uz

Submission #235441

# Submission time Handle Problem Language Result Execution time Memory
235441 2020-05-28T09:33:42 Z VEGAnn San (COCI17_san) C++14
120 / 120
 260 ms 25308 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
using namespace std;
typedef long long ll;
const int N = 45;
const int PW = 22;
const int oo = 2e9;
vector<int> fen;
vector<ll> vls[N], vc;
ll h[N], g[N], k, sum[(1 << PW)], ans = 0, glob;
int n, mid, nm[N];

void calc(int l, int r){
    int len = (r - l + 1);

    fill(sum, sum + (1 << len), -1);

    sum[0] = 0;

    for (int msk = 0; msk < (1 << len); msk++){
        if (sum[msk] < 0) continue;

        if (sum[msk] >= k)
            ans++;

        int fi = 0, se = len - 1;

        while (fi < len && !(msk & (1 << fi)))
            fi++;

        while (se >= 0 && !(msk & (1 << se)))
            se--;

        for (int i = 0; i < len; i++)
            if (!(msk & (1 << i))){
                int id = i + l;
                ll nw_sum = sum[msk] + g[id];
                int nmsk = (msk | (1 << i));

                if (sum[nmsk] > 0) continue;

                if (msk == 0){
                    vls[i + l].PB(nw_sum);
                    sum[nmsk] = nw_sum;
                } else {
                    if (l == 0){
                        if (i > se && h[id] >= h[se + l]){
                            vls[i + l].PB(nw_sum);
                            sum[nmsk] = nw_sum;
                        }
                    } else {
                        if (i > se && h[id] >= h[se + l]){
                            vls[l + fi].PB(nw_sum);
                            sum[nmsk] = nw_sum;
                        }
                    }
                }
            }
    }
}

bool cmp(int _x, int _y){
    return h[_x] > h[_y];
}

void update(ll x){
    int loc = lower_bound(all(vc), x) - vc.begin();

    glob++;

    for (; loc < sz(fen); loc = (loc | (loc + 1)))
        fen[loc]++;
}

ll summa(ll x){
    int loc = lower_bound(all(vc), x) - vc.begin() - 1;
    ll res = 0;

    for (; loc >= 0; loc = (loc & (loc + 1)) - 1)
        res += fen[loc];

    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> h[i] >> g[i];
        nm[i] = i;
    }

    if (n == 1){
        cout << (g[0] >= k ? 1 : 0);
        return 0;
    }

    mid = n / 2;

    calc(0, mid - 1);

    calc(mid, n - 1);

    for (int i = mid; i < n; i++)
    for (ll cr : vls[i])
        vc.PB(cr);

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    fen.resize(sz(vc));
    fill(all(fen), 0);

    sort(nm, nm + mid, cmp);
    sort(nm + mid, nm + n, cmp);

    int ite = 0;

    for (int i = 0, ptr = mid; i < mid; i++){
        while (ptr < n && h[nm[ptr]] >= h[nm[i]]){
            for (ll cr : vls[nm[ptr]])
                update(cr);
            ptr++;
        }

        for (ll cr : vls[nm[i]]){
            ll ost = k - cr;

            ans += glob - summa(ost);
        }
    }

    cout << ans;

    return 0;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:129:9: warning: unused variable 'ite' [-Wunused-variable]
     int ite = 0;
         ^~~

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2488 KB Output is correct
2 Correct 6 ms 1024 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6192 KB Output is correct
2 Correct 12 ms 4864 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 25308 KB Output is correct
2 Correct 31 ms 10608 KB Output is correct