Submission #615532

#	Time	Username	Problem	Language	Result	Execution time	Memory
615532		fvogel499	Meetings (IOI18_meetings)	C++17	17 / 100	196 ms	43944 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(x) (int)((x).size())

const int p2 = 1<<20;
const int siz = 750*1000+40;

struct Segtree {
    Segtree() {
        t = new int [p2*2];
        lz = new int [p2*2];
        for (int i = 0; i < p2*2; i++) {
            t[i] = lz[i] = 0;
        }
    }
    void push(int x) {
        if (x < p2) {
            lz[x*2] += lz[x];
            lz[x*2+1] += lz[x];
        }
        t[x] += lz[x];
        lz[x] = 0;
    }
    void pull(int x) {
        t[x] = max(t[x*2], t[x*2+1]);
    }
    void upd(int rb, int re, int rv, int qn = 1, int qb = 0, int qe = p2-1) {
        if (rb > qe || qb > re) push(qn);
        else if (rb <= qb && qe <= re) {
            lz[qn] += rv;
            push(qn);
        }
        else {
            push(qn);
            int qm = (qb+qe)/2;
            upd(rb, re, rv, qn*2, qb, qm);
            upd(rb, re, rv, qn*2+1, qm+1, qe);
            pull(qn);
        }
    }
    int get(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
        push(qn);
        if (rb > qe || qb > re) return 0;
        else if (rb <= qb && qe <= re) return t[qn];
        else {
            int qm = (qb+qe)/2;
            int r = max(get(rb, re, qn*2, qb, qm), get(rb, re, qn*2+1, qm+1, qe));
            pull(qn);
            return r;
        }
    }
    int* t, * lz;
};

std::vector<int> minimum_costs(std::vector<signed> b, std::vector<signed> queryL, std::vector<signed> queryR) {
    const int n = sz(b);
    const int nbQ = sz(queryL);
    vector<int> queryAt [n];
    for (int i = 0; i < nbQ; i++) queryAt[queryR[i]].push_back(i);
    vector<int> res(nbQ, -1);
    Segtree st = Segtree();
    int consOnes = 0;
    for (int i = 0; i < n; i++) {
        if (b[i] == 1) consOnes++;
        else consOnes = 0;
        if (consOnes > 0) {
            assert(i-consOnes+1 >= 0);
            st.upd(i-consOnes+1, i, 1);
        }
        for (int j : queryAt[i]) {
            res[j] = st.get(queryL[j], queryR[j]);
        }
    }
    for (int i = 0; i < nbQ; i++) {
        assert(res[i] != -1);
        res[i] = 2*(queryR[i]-queryL[i]+1)-res[i];
    }
    return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40