Submission #1112233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112233		PagodePaiva	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	3 ms	8784 KiB

fortune_telling2

    #include<bits/stdc++.h>
    //#define int long long
    #define fr first
    #define sc second
     
    using namespace std;
     
    const int N = 200010;
    const int B = 200;
    int v[N][2];
    int blocks[N];
     
    struct Segtree{
        pair <int, int> tree[4*N]; int lazy[4*N];
        pair <int, int> join(pair <int, int> a, pair <int, int> b){
            return {max(a.fr, b.fr), max(a.sc, b.sc)};
        }
        void unlazy(int node, int l, int r){
            if(lazy[node]%2) swap(tree[node].fr, tree[node].sc);
            if(l != r){
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }
            lazy[node] = 0;
        }
        void build(int node, int l, int r){
            lazy[node] = 0;
            if(l == r){
                tree[node] = {v[l][0], v[l][1]};
                return;
            }
            int mid = (l+r)/2;
            build(2*node, l, mid);
            build(2*node+1, mid+1, r);
            tree[node] = join(tree[2*node], tree[2*node+1]);
        }
        void update(int node, int l, int r, int tl, int tr, int val){
            unlazy(node, tl, tr);
            if(l > tr or tl > r) return;
            if(l <= tl and tr <= r){
                if(tree[node].first <= val) {
                    lazy[node]++;
                    unlazy(node, tl, tr);
                    return;
                }
                else{
                    int mid = (tl+tr)/2;
                    if(tl == tr) return;
                    update(2*node, l, r, tl, mid, val);
                    update(2*node+1, l, r, mid+1, tr, val);
                    tree[node] = join(tree[2*node], tree[2*node+1]);
                }
                return;
            }
            int mid = (tl+tr)/2;
            update(2*node, l, r, tl, mid, val);
            update(2*node+1, l, r, mid+1, tr, val);
            tree[node] = join(tree[2*node], tree[2*node+1]);
            return;
        }
        pair <int, int> query(int node, int l, int r, int tl, int tr){
            unlazy(node, tl, tr);
            if(l > tr or tl > r) return {0, 0};
            if(l <= tl and tr <= r) return tree[node];
            int mid = (tl+tr)/2;
            return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
        }
    } seg;
     
    bool comp2(array <int, 3> a, array <int, 3> b){
        if(blocks[a[2]] > blocks[b[2]]) return false;
        if(blocks[a[2]] < blocks[b[2]]) return true;
        if(max(a[0], a[1]) < max(b[0], b[1])) return true;
        return false;
    }
     
    bool comp(array <int, 3> a, array <int, 3> b){
        if(max(a[0], a[1]) < max(b[0], b[1])) return true;
        return false;
    }
     
    int32_t main(){
        ios::sync_with_stdio(false); cin.tie(0);
        int n, k;
        cin >> n >> k;
        vector <array <long long, 3>> vvv;
        vector <int> valores;
        map <int, int> voltar;
        for(long long i = 1;i <= n;i++){
            long long a, b;
            cin >> a >> b;
            vvv.push_back({a, b, i});
            valores.push_back(a);
            valores.push_back(b);
        }
        map <long long, int> compressao;
        vector <int> qr;
        for(int i = 0;i < k;i++){
            int q;
            cin >> q;
            qr.push_back(q);
            valores.push_back(q);
        }
        sort(valores.begin(), valores.end());
        for(int i = 0;i < valores.size();i++){
            compressao[valores[i]] = i+1;
            voltar[i+1] = valores[i];
        }
        vector <array <int, 3>> vv;
        for(auto &x : vvv){
            x[0] = compressao[x[0]];
            x[1] = compressao[x[1]];
            array <int, 3> aux;
            aux[0] = x[0];
            aux[1] = x[1];
            aux[2] = x[2];
            vv.push_back(aux);
        }
        for(auto &x : qr){
            x = compressao[x];
        }
        sort(vv.begin(), vv.end(), comp);
        for(int i = 1;i <= n;i++){
            blocks[vv[i-1][2]] = i/B;
        }
        sort(vv.begin(), vv.end(), comp2);
        for(int i = 0;i < n;i++){
            v[i+1][0] = vv[i][0];
            v[i+1][1] = vv[i][1];
            //cout << v[i+1][0] << ' ' << v[i+1][1] << '\n';
        }
        seg.build(1,1, n);
        for(int i = 0;i < k;i++){
            int q = qr[i];
            seg.update(1, 1, n, 1, n, q);
        }
        int res = 0;
        for(int i = 1;i <= n;i++){
            res += voltar[seg.query(1, i, i, 1, n).first];  
        }
        cout << res << '\n';
    }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:105:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i = 0;i < valores.size();i++){
      |                       ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65