Submission #985392

#	Time	Username	Problem	Language	Result	Execution time	Memory
985392		nnin	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5045 ms	13680 KiB

street_lamps

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

int n, q;
bool status[300005];

struct segTree {
    struct node {
        int val;
        node *left, *right;
        node() {
            val = 0;
            left = right = NULL;
        }
    };
    node *root;
    segTree() {
        root = new node();
    }
    void update(node *cur, int l, int r, int wl, int wr, int v) {
        if(wl<=l && wr>=r) {
            cur->val += v;
            return;
        }
        int m = (l+r)/2;
        if(wl<=m) {
            if(!cur->left) cur->left = new node();
            update(cur->left, l, m, wl, wr, v);
        }
        if(wr>m) {
            if(!cur->right) cur->right = new node();
            update(cur->right, m+1, r, wl, wr, v);
        }
    }
    void update(int wl, int wr, int v) {update(root, 0, n, wl, wr, v);}
    int query(node *cur, int l, int r, int x) {
        int ret = cur->val;
        if(l==r) return ret;
        int m = (l+r)/2;
        if(x<=m && cur->left) return ret+query(cur->left, l, m, x);
        if(x>m && cur->right) return ret+query(cur->right, m+1, r, x);
        return ret;
    }
    int query(int x) {return query(root, 0, n, x);}
};

struct segTree2 {
    struct node2 {
        segTree *tree;
        node2 *left, *right;
        node2() {
            tree = new segTree();
            left = right = NULL;
        }
    };
    node2 *root;
    segTree2() {
        root = new node2();
    }
    void update(node2 *cur, int l, int r, int wl, int wr, int wll, int wrr, int v) {
        if(wl<=l && wr>=r) {
            cur->tree->update(wll, wrr, v);
            return;
        }
        int m = (l+r)/2;
        if(wl<=m) {
            if(!cur->left) cur->left = new node2();
            update(cur->left, l, m, wl, wr, wll, wrr, v);
        }
        if(wr>m) {
            if(!cur->right) cur->right = new node2();
            update(cur->right, m+1, r, wl, wr, wll, wrr, v);
        }
    }
    void update(int wl, int wr, int wll, int wrr, int v) {update(root, 0, n, wl, wr, wll, wrr, v);}
    int query(node2 *cur, int l, int r, int x, int xx) {
        int ret = cur->tree->query(xx);
        if(l==r) return ret;
        int m = (l+r)/2;
        if(x<=m && cur->left) return ret+query(cur->left, l, m, x, xx);
        if(x>m && cur->right) return ret+query(cur->right, m+1, r, x, xx);
        return ret;
    }
    int query(int x, int xx) {return query(root, 0, n, x, xx);}
} *seg;

set<pii> range;

pii func01(int x) {
    int l = x, r = x;
    auto it = upper_bound(range.begin(), range.end(), make_pair(x, x));
    if(it!=range.end() && it->first==x+1) {
        r = it->second;
        range.erase(it);
    }
    it = lower_bound(range.begin(), range.end(), make_pair(x, x));
    if(it!=range.begin() && prev(it)->second==x-1) {
        it--;
        l = it->first;
        range.erase(it);
    }
    range.insert({l, r});
    return {l, r};
}
pii func10(int x) {
    auto it = upper_bound(range.begin(), range.end(), make_pair(x, (int)1e9));
    it--;
    auto [l, r] = *it;
    range.erase(it);
    if(l<x) range.insert({l, x-1});
    if(r>x) range.insert({x+1, r});
    return {l, r};
}

bool inrange(int l, int r) {
    auto it = upper_bound(range.begin(), range.end(), make_pair(l, (int)1e9));
    if(it==range.begin()) return 0;
    it--;
    return it->second>=r;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    string s;
    cin>>s;
    int st = -1;
    for(int i=1;i<=n;i++) {
        status[i] = s[i-1]-'0';
        if(status[i]==0 && st!=-1) {
            range.insert({st, i-1});
            st = -1;
        } else if(status[i]==1 && st==-1) {
            st = i;
        }
    }
    seg = new segTree2();
    if(st!=-1) range.insert({st, n});
    for(int i=1;i<=q;i++) {
        cin>>s;
        if(s[0]=='q') {
            int a, b;
            cin>>a>>b;
            int ans = 0;
            if(inrange(a, b-1)) ans = i;
            ans += seg->query(a, b-1);
            cout<<ans<<'\n';
        } else {
            int a;
            cin>>a;
            if(status[a]==0) {
                auto [l, r] = func01(a);
                seg->update(l, a, a, r, -i);
            } else {
                auto [l, r] = func10(a);
                seg->update(l, a, a, r, i);
            }
            status[a] = !status[a];
        }
    }
}

/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Compilation message (stderr)

street_lamps.cpp: In function 'std::pair<int, int> func10(int)':
street_lamps.cpp:109:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |     auto [l, r] = *it;
      |          ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:153:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |                 auto [l, r] = func01(a);
      |                      ^
street_lamps.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |                 auto [l, r] = func10(a);
      |                      ^

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