oj.uz

Submission #52178

# Submission time Handle Problem Language Result Execution time Memory
52178 2018-06-24T14:04:57 Z EntityIT San (COCI17_san) C++14
48 / 120
 1000 ms 30672 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MAX = 2500005;
int n, h[2][25], g[2][25], m[2], K, ans, cnt;
vector<int> vec[2];
map<int,vector<int> > mp[2];
map<int, int> lab;
set<int> gold;
struct BIT {
    int v[MAX];
    void update(int _pos) {
        for (; _pos < MAX; _pos += _pos&-_pos) v[_pos]++;
    }
    int get(int _pos) {
        int res = 0;
        for (; _pos; _pos -= _pos&-_pos) res += v[_pos];
        return res;
    }
} bit;

void sieve(int id) {
    for (int mask = 1; mask < (1 << m[id]); ++mask) {
        vector<int> x;
        int c = 0;
        for (int i = 0; i < m[id]; ++i) {
            if ( (mask >> i) & 1 ) x.push_back(h[id][i]), c += g[id][i];
        }
        bool ok = 1;
        for (int i = 0; i < x.size() - 1; ++i) {
            if (x[i] > x[i + 1]) { ok = 0; break; }
        }
        if (!ok) continue;
        int _h = (id ? x[0] : x.back() );
        vec[id].push_back(_h);
        mp[id][_h].push_back(c);
        if (c >= K) ans++;
        gold.insert(c);
    }
    sort(vec[id].begin(), vec[id].end() );
    vec[id].erase (unique (vec[id].begin(), vec[id].end()), vec[id].end() );
}

void upd (int pter) {
    for (auto go : mp[1][pter]) {
        bit.update(lab[go]);
    }
}

void ge (int _gold) {
    set<int>::iterator it = gold.lower_bound (K - _gold);
    ans += bit.get (cnt) - bit.get (lab[*it] - 1);
}

signed main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> K;
    m[0] = n / 2; m[1] = n- m[0];
    for (int i = 0; i < n; ++i) {
        int _h, _g; cin >> _h >> _g;
        if (i < m[0]) {
            h[0][i] = _h; g[0][i] = _g;
        }
        else {
            h[1][i - m[0] ] = _h; g[1][i - m[0] ] = _g;
        }
    }

    sieve(0); sieve(1);

    for (int go : gold) {
        lab[go] = ++cnt;
    }

    int pter = vec[1].size() - 1;
    for (int i = vec[0].size() - 1; i >= 0; --i) {
        while (pter >= 0 && vec[1][pter] >= vec[0][i]) {
            upd (vec[1][pter]);
            pter--;
        }
        for (int j = 0; j < mp[0][ vec[0][i] ].size(); ++j) {
            ge (mp[0][ vec[0][i] ][j]);
        }
    }

    cout << ans;

    return  0;
}

Compilation message

san.cpp: In function 'void sieve(long long int)':
san.cpp:33:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < x.size() - 1; ++i) {
                         ~~^~~~~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:84:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < mp[0][ vec[0][i] ].size(); ++j) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1008 KB Output is correct
2 Runtime error 5 ms 1008 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 14052 KB Output is correct
2 Correct 45 ms 14052 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 25176 KB Output is correct
2 Correct 377 ms 25176 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 30672 KB Time limit exceeded
2 Halted 0 ms 0 KB -