Submission #1032813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032813		caterpillow	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2612 ms	291720 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

inline namespace FastIO {
    const int BSZ = 1 << 15;
    char ibuf[BSZ]; int ipos, ilen;
    char nc() {
        if (ipos == ilen) {
            ipos = 0; 
            ilen = fread(ibuf,1,BSZ,stdin);
            if (!ilen) return EOF;
        }
        return ibuf[ipos++];
    }
    void rs(string& x) {
        char ch; while (isspace(ch = nc()));
        do { x += ch; } while (!isspace(ch = nc()) && ch != EOF);
    }
    template<class T> void ri(T& x) {
        char ch; 
        int sgn = 1;
        while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1;
        x = ch - '0'; 
        while (isdigit(ch = nc())) x = x * 10 + (ch - '0');
        x *= sgn;
    }
    template<class T, class... Ts> void ri(T& t, Ts&... ts) { ri(t); ri(ts...); } 
    char obuf[BSZ], numBuf[100]; int opos;
    void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
    void wc(char c) {
        if (opos == BSZ) flushOut();
        obuf[opos++] = c; 
    }
    void ws(string s) { for (char& c : s) wc(c); }
    template<class T> void wi(T x, char after = '\0') {
        if (x < 0) wc('-'), x *= -1;
        int len = 0; 
        for (; x >= 10; x /= 10) numBuf[len++] = '0' + (x % 10);
        wc('0' + x); 
        ROF (i, 0, len) wc(numBuf[i]);
        if (after) wc(after);
    }
    void initO() { assert(atexit(flushOut) == 0); }
}

using namespace FastIO;
namespace treap {
    struct Node {
        int l, r;
        int i;
        ll val, lazy;
        int lo, hi;
    };

    int n = 1;
    Node nodes[10000000];

    inline int make(int i, int l, int r) {
        nodes[n] = {l, r, i, 0, 0, l ? nodes[l].lo : i, r ? nodes[r].hi : i};
        return n++;
    }

    void inc(int n, int lo, int hi, ll v) {
        if (!n) return;
        if (lo > nodes[n].hi || hi < nodes[n].lo) return;
        if (lo <= nodes[n].lo && nodes[n].hi <= hi) {
            nodes[n].lazy += v;
            return;
        }
        if (lo <= nodes[n].i && nodes[n].i <= hi) nodes[n].val += v;
        inc(nodes[n].l, lo, hi, v);
        inc(nodes[n].r, lo, hi, v);
    }

    ll query(int n, int i) {
        if (nodes[n].i == i) return nodes[n].val + nodes[n].lazy;
        if (i <= nodes[n].i) return nodes[n].lazy + query(nodes[n].l, i);
        else return nodes[n].lazy + query(nodes[n].r, i);
    }

    int build(vt<int>& a, int l, int r) {
        if (l > r) return 0;
        int m = (l + r) / 2;
        return make(a[m], build(a, l, m - 1), build(a, m + 1, r));
    }
}

struct SegTree {
    int n;
    vt<vt<int>> todo;
    vt<int> seg;
    void init(int _n) {
        n = _n;
        todo.resize(2 * n);
        seg.resize(2 * n);
    }
    void load(int l, int r) {
        todo[l += n].pb(r);
        while (l /= 2) todo[l].pb(r);
    }
    void build() {
        FOR (i, 1, 2 * n) {
            seg[i] = treap::build(todo[i], 0, size(todo[i]) - 1);
        }
    }
    void upd(int l1, int l2, int r1, int r2, int v) {
        for (l1 += n, l2 += n + 1; l1 < l2; l1 >>= 1, l2 >>= 1) {
            if (l1 & 1) treap::inc(seg[l1++], r1, r2, v);
            if (l2 & 1) treap::inc(seg[--l2], r1, r2, v);
        }
    } 
    ll query(int l, int r) {
        ll res = treap::query(seg[l += n], r);
        while (l /= 2) res += treap::query(seg[l], r);
        return res;
    }
};

using ull = unsigned long long;
const int depth = 4;
const int sz = 1 << (depth * 6);

struct Tree {
    vt<ull> seg[depth];
    
    Tree() {
        F0R (i, depth) seg[i].resize(1 << (6 * i));
    }

    void insert(int x) {
        ROF (d, 0, depth) {
            seg[d][x >> 6] |= 1ull << (x & 63);
            x >>= 6;
        }
    } 

    void erase(int x) {
        ull b = 0;
        ROF (d, 0, depth) {
            seg[d][x >> 6] &= ~(1ull << (x & 63));
            seg[d][x >> 6] |= b << (x & 63);
            x >>= 6;
            b = bool(seg[d][x]);
        }
    }

    int next(int x) {
        if (x >= sz) return sz;
        x = std::max(x, 0);
        int d = depth - 1;
        while (true) {
            if (ull m = seg[d][x >> 6] >> (x & 63)) {
                x += __builtin_ctzll(m);
                break;
            }
            x = (x >> 6) + 1;
            if (d == 0 || x >= (1 << (6 * d))) return sz;
            d--;
        }
        while (++d < depth) {
            x = (x << 6) + __builtin_ctzll(seg[d][x]);
        }
        return x;
    }

    int prev(int x) {
        if (x < 0) return -1;
        x = std::min(x, sz - 1);
        int d = depth - 1;
        while (true) {
            if (ull m = seg[d][x >> 6] << (63 - (x & 63))) {
                x -= __builtin_clzll(m);
                break;
            }
            x = (x >> 6) - 1;
            if (d == 0 || x == -1) return -1;
            d--;
        }
        while (++d < depth) {
            x = (x << 6) + 63 - __builtin_clzll(seg[d][x]);
        }
        return x;
    }

    int min() {
        if (empty()) return sz;
        int ans = 0;
        F0R (d, depth) {
            ans <<= 6;
            ans += __builtin_ctzll(seg[d][ans >> 6]);
        }
        return ans;
    }

    int max() {
        if (empty()) return -1;
        int ans = 0;
        F0R (d, depth) {
            ans <<= 6;
            ans += 63 - __builtin_clzll(seg[d][ans >> 6]);
        }
        return ans;
    }

    inline bool empty() { return !seg[0][0]; }
    inline int operator[](int i) { return 1 & (seg[depth - 1][i >> 6] >> (i & 63)); }
};

main() {
    cin.tie(0)->sync_with_stdio(0);

    initO();
    
    int n, q; ri(n, q);
    Tree dead;
    F0R (i, n) if (nc() == '0') dead.insert(i);
    dead.insert(n);

    vt<pi> queries(q);
    vt<pi> pts;
    pts.reserve(q);
    
    F0R (i, q) {
        string t; rs(t);
        if (t[0] == 'q') {
            int l, r; ri(l, r); l--, r--;
            queries[i] = {l, r - 1};
            pts.emplace_back(r - 1, l);
        } else if (t[0] == 't') {
            int j; ri(j);
            queries[i] = {j - 1, -1};
        } else assert(0);
    }

    sort(all(pts));
    pts.erase(unique(all(pts)), pts.end());

    SegTree seg; 
    seg.init(n);
    for (auto [r, l] : pts) seg.load(l, r);
    seg.build();

    int t = 0;
    for (auto [x, y] : queries) {
        t++;
        if (y == -1) {
            if (dead[x] == 1) {
                dead.erase(x);
                seg.upd(dead.prev(x) + 1, x, x, dead.next(x) - 1, -t);
            } else {
                seg.upd(dead.prev(x) + 1, x, x, dead.next(x) - 1, t);
                dead.insert(x);
            }
        } else {
            if (dead.next(x) > y) {
                wi(seg.query(x, y) + t, '\n');
            } else {
                wi(seg.query(x, y), '\n');
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp:230:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  230 | main() {
      | ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20