oj.uz

Submission #197108

# Submission time Handle Problem Language Result Execution time Memory
197108 2020-01-18T20:00:47 Z Anai Street Lamps (APIO19_street_lamps) C++14
20 / 100
 709 ms 90236 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using pii = pair<int, int>;

const int N = 3e5 + 5;

struct Iv {
    int st, dr, val;
};

struct Query {
    int st, dr, idx;
};

struct Update {
    int pos, idx;
};

class SegTree {
    struct Nod {
        int st, dr;
        int lazy, sum;
    };

    vector<Nod> acc;
    int pom[N * 5];
    int ql, qr, qval, qh;

    int make_nod() {
        acc.push_back({0, 0, 0, 0});
        return acc.size() - 1;
    }

    void prop(int nod, int st, int dr) {
        if (acc[nod].st == 0) acc[nod].st = make_nod();
        if (acc[nod].dr == 0) acc[nod].dr = make_nod();
        acc[nod].sum+= acc[nod].lazy * (dr - st + 1);
        acc[acc[nod].st].lazy+= acc[nod].lazy;
        acc[acc[nod].dr].lazy+= acc[nod].lazy;
        acc[nod].lazy = 0;
    }

    int eval(int nod, int st, int dr) {
        return acc[nod].sum + (dr - st + 1) * acc[nod].lazy;
    }

    int update_deep(int nod, int st, int dr) {
        if (nod == 0) nod = make_nod();
        if (ql <= st && dr <= qr) {
            acc[nod].lazy+= qval;
            return nod;
        }
        int mid = (st + dr) / 2;
        prop(nod, st, dr);
        if (ql <= mid)
            acc[nod].st = update_deep(acc[nod].st, st, mid);
        if (mid < qr)
            acc[nod].dr = update_deep(acc[nod].dr, mid + 1, dr);
        acc[nod].lazy = 0;
        acc[nod].sum = eval(acc[nod].st, st, mid) + eval(acc[nod].dr, mid + 1, dr);
        return nod;
    }

    void update_shallow(int nod, int st, int dr) {
        pom[nod] = update_deep(pom[nod], 0, N);
        if (st == dr)
            return;
        int mid = (st + dr) / 2;
        if (qh <= mid)
            update_shallow(2 * nod, st, mid);
        else
            update_shallow(2 * nod + 1, mid + 1, dr);
    }

    pii query_deep(int nod, int st, int dr) {
        if (nod == 0) nod = make_nod();
        if (ql <= st && dr <= qr)
            return pii(nod, eval(nod, st, dr));

        int mid = (st + dr) / 2, ans = 0;
        prop(nod, st, dr);
        if (ql <= mid) {
            pii ret = query_deep(acc[nod].st, st, mid);
            acc[nod].st = ret.x;
            ans+= ret.y;
        }
        if (mid < qr) {
            pii ret = query_deep(acc[nod].dr, mid + 1, dr);
            acc[nod].dr = ret.x;
            ans+= ret.y;
        }
        return pii(nod, ans);
    }

    int query_shallow(int nod, int st, int dr) {
        if (st > qh)
            return 0;
        if (dr <= qh)
            return query_deep(pom[nod], 0, N).y;
        int ans = 0, mid = (st + dr) / 2;
        ans+= query_shallow(2 * nod, st, mid);
        ans+= query_shallow(2 * nod + 1, mid + 1, dr);
        return ans;
    }

public:
    void update(int st, int dr, int h, int val) {
        ql = st, qr = dr, qh = h, qval = val;
        update_shallow(1, 0, N);
    }

    int query(int st, int dr, int h) {
        ql = st, qr = dr, qh = h;
        return query_shallow(1, 0, N);
    }

    SegTree() {
        acc.reserve(N * 8);
        acc.push_back({0, 0, 0, 0});
    }
};

inline bool operator < (const Iv &a, const Iv &b) { return a.st < b.st; }

vector<int> upd;
char str[N];
int ans[N];

set<Iv> s;
vector<Query> qs;
vector<Update> ups;
SegTree magic;
int n, q;

static void apply(int newh, int st, int dr) {
    if (st > dr)
        return;
    auto it = prev(s.upper_bound(Iv {st, st, st}));
    Iv fst, lst;
    fst = lst = *it;
    for (; it != end(s) && it->st <= dr;) {
        lst = *it;
        auto inc = next(it);
        magic.update(it->st, it->dr, it->val, -1);
        s.erase(it);
        it = inc;
    }

    magic.update(st, dr, newh, 1);
    s.insert(Iv {st, dr, newh});
    if (fst.st <= st - 1) {
        magic.update(fst.st, st - 1, fst.val, 1);
        s.insert(Iv {fst.st, st - 1, fst.val});
    }
    if (dr + 1 <= lst.dr) {
        magic.update(dr + 1, lst.dr, lst.val, 1);
        s.insert(Iv {dr + 1, lst.dr, lst.val});
    }
}

int main() {
#ifdef HOME
    freopen("streetlights.in", "r", stdin);
    freopen("streetlights.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int ptru(0), ptrq(0);

    cin >> n >> q >> (str + 1);
    upd.reserve(2 * N);
    qs.reserve(N);
    for (int i = 1; i <= q; ++i) {
        string op;
        cin >> op;
        if (op == "query") {
            int l, r;
            cin >> l >> r;
            qs.push_back({l, r - 1, i});
        }
        else {
            int pos;
            cin >> pos;
            ups.push_back({pos, i});
        }
    }
    for (int i = 1; i <= n; ++i)
        if (str[i] == '0')
            ups.push_back({i, 0});

    sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return pii(a.dr, a.idx) < pii(b.dr, b.idx); });
    sort(begin(ups), end(ups), [&](const Update &a, const Update &b) { return pii(a.pos, a.idx) < pii(b.pos, b.idx); });

    s.insert(Iv {0, q, 1});
    magic.update(0, q, 1, 1);

    for (int i = 1; i <= n; ++i) {
        vector<pii> upd;
        bool par = true;
        int lst_tid = -1; 

        while (ptru < ups.size() && ups[ptru].pos <= i) {
            upd.emplace_back(lst_tid + 1, ups[ptru].idx);
            lst_tid = ups[ptru].idx;
            ptru+= 1;
        }
        upd.emplace_back(lst_tid + 1, q);

        for (int j = 1; j < upd.size(); j+=2) {
            apply(i + 1, upd[j].x, upd[j].y);
        }

        while (ptrq < qs.size() && qs[ptrq].dr <= i) {
            ans[qs[ptrq].idx] = magic.query(1, qs[ptrq].idx, qs[ptrq].st);
            ptrq+= 1;
        }
    }

    sort(begin(qs), end(qs), [&](const Query &a, const Query &b) {
        return a.idx < b.idx; });

    for (auto i: qs)
        cout << ans[i.idx] << '\n';

    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:205:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptru < ups.size() && ups[ptru].pos <= i) {
                ~~~~~^~~~~~~~~~~~
street_lamps.cpp:212:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < upd.size(); j+=2) {
                         ~~^~~~~~~~~~~~
street_lamps.cpp:216:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptrq < qs.size() && qs[ptrq].dr <= i) {
                ~~~~~^~~~~~~~~~~
street_lamps.cpp:202:14: warning: unused variable 'par' [-Wunused-variable]
         bool par = true;
              ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3800 KB Output is correct
2 Correct 36 ms 3320 KB Output is correct
3 Correct 25 ms 2752 KB Output is correct
4 Correct 9 ms 3320 KB Output is correct
5 Runtime error 581 ms 87500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2424 KB Output is correct
2 Correct 28 ms 2872 KB Output is correct
3 Correct 37 ms 3300 KB Output is correct
4 Correct 46 ms 3836 KB Output is correct
5 Runtime error 709 ms 90236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Runtime error 596 ms 85744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -