oj.uz

Submission #615532

# Submission time Handle Problem Language Result Execution time Memory
615532 2022-07-31T10:20:44 Z fvogel499 Meetings (IOI18_meetings) C++17
17 / 100
 196 ms 43944 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33028 KB Output is correct
2 Correct 62 ms 35952 KB Output is correct
3 Correct 141 ms 42536 KB Output is correct
4 Correct 172 ms 42532 KB Output is correct
5 Correct 132 ms 43636 KB Output is correct
6 Correct 147 ms 43944 KB Output is correct
7 Correct 196 ms 42588 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33028 KB Output is correct
2 Correct 62 ms 35952 KB Output is correct
3 Correct 141 ms 42536 KB Output is correct
4 Correct 172 ms 42532 KB Output is correct
5 Correct 132 ms 43636 KB Output is correct
6 Correct 147 ms 43944 KB Output is correct
7 Correct 196 ms 42588 KB Output is correct
8 Incorrect 145 ms 42500 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 33108 KB Output isn't correct
2 Halted 0 ms 0 KB -