Submission #538395

#	Time	Username	Problem	Language	Result	Execution time	Memory
538395		Evang	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	1738 ms	524288 KiB

street_lamps

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 3e5+5;
int n2, n=1, q;

struct node {
    node *le=nullptr, *ri=nullptr;
    ll sum = 0;
    node *l() {
        if(le==nullptr)
            le = new node;
        return le;
    }
    node *r(){
        if(ri==nullptr)
            ri = new node;
        return ri;
    }
};
using pnode = node*;

void upd(int c, pnode v, int x){
    int l = 1, r = n;
    v->sum += x;
    while(l<r){
        int m = (l+r)/2;
        if(c<=m){
            v = v->l();
            r = m;
        }else{
            v = v->r();
            l = m+1;
        }
        v->sum += x;
    }
}

ll qry(int l, int r, pnode v, int il, int ir){
    if(ir < l || r < il)
        return 0;
    if(l <= il && ir <= r)
        return v->sum;

    int im = (il+ir)/2;
    return qry(l, r, v->l(), il, im) + qry(l, r, v->r(), im+1, ir);
}

ll qry(int l, int r, pnode v){
    return qry(l, r, v, 1, n);
}

struct segtree {
    pnode tr[2*N];

    void upd(int r, int c, int x){
        // add x to point (r, c)
        // r and c are 1-indexed
        r += n2-1;
        while(r>0){
            if(tr[r]==nullptr)
                tr[r] = new node;
            ::upd(c, tr[r], x);
            r /= 2;
        }
    }

    ll qry(int l, int r, int l2, int r2){
        ll ans = 0;
        l += n2-1;
        r += n2-1;
        while(l<=r){
            if(l&1) {
                if(tr[l]==nullptr)
                    tr[l] = new node;
                ans += ::qry(l2, r2, tr[l]);
                l++;
            }
            if(r&1^1) {
                if(tr[r]==nullptr)
                    tr[r] = new node;
                ans += ::qry(l2, r2, tr[r]);
                r--;
            }
            l /= 2; r /= 2;
        }
        return ans;
    }
} seg;  // seg represents the x-coordinates

void upd(int x1, int x2, int y1, int y2, int v){
    ++x2; ++y2;
    seg.upd(x1, y1, v);
    seg.upd(x2, y1, -v);
    seg.upd(x1, y2, -v);
    seg.upd(x2, y2, v);
}

ll get(int x, int y){
    return seg.qry(1, x, 1, y);
}

struct BIT {
    int bit[N];
    void upd(int i, int x){
        while(i<=n2){
            bit[i] += x;
            i += i&-i;
        }
    }
    int sum(int r){
        int ans = 0;
        while(r>0){
            ans += bit[r];
            r -= r&-r;
        }
        return ans;
    }
    int qry(int l, int r){
        return sum(r) - sum(l-1);
    }
} bit;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n2 >> q;
    while(n<n2)
        n *= 2;

    for(int i = 1; i <= n2; ++i){
        char c;
        cin >> c;
        if(c=='1')
            bit.upd(i, 1);
    }

    for(int i = 1; i <= q; ++i){
        str t;
        cin >> t;
        if(t=="query"){
            int l, r;
            cin >> l >> r;
            --r;
            ll ans = get(l, r);
            if(bit.qry(l, r)==r-l+1)
                ans += i;
            cout << ans << el;
        }else{
            int e;
            cin >> e;
            int l = e, r = e;
            for(int u = n; u > 0; u/= 2){
                while(l-u>0&&bit.qry(l-u, e-1)==e-(l-u))
                    l -= u;
                while(r+u<=n&&bit.qry(e+1,r+u)==r+u-e)
                    r += u;
            }

            if(bit.qry(e, e)==1) {
                upd(l, e, e, r, i);
                bit.upd(e, -1);
            }
            else {
                upd(l, e, e, r, -i);
                bit.upd(e, 1);
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In member function 'll segtree::qry(int, int, int, int)':
street_lamps.cpp:137:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  137 |             if(r&1^1) {
      |                ~^~

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