Submission #52179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
52179	2018-06-24T14:16:42 Z	EntityIT	San (COCI17_san)	C++14	Compilation error	0 ms	0 KB

san

#include<bits/stdc++.h>

using namespace std;

const int MAX = 2500005;
int n, h[2][25], g[2][25], m[2], K;
long long cnt, ans;
vector<int> vec[2];
map<int,vector<long long> > mp[2];
map<long long, long long> lab;
set<long long> 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(int)':
san.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < x.size() - 1; ++i) {
                         ~~^~~~~~~~~~~~~~
san.cpp: In function 'void ge(int)':
san.cpp:53:46: error: conversion from 'std::set<long long int>::iterator {aka std::_Rb_tree_const_iterator<long long int>}' to non-scalar type 'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' requested
     set<int>::iterator it = gold.lower_bound (K - _gold);
                             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:83:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < mp[0][ vec[0][i] ].size(); ++j) {
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~