Submission #257738

#	Time	Username	Problem	Language	Result	Execution time	Memory
257738		2qbingxuan	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	526 ms	76244 KiB

street_lamps

#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template<typename H, typename ...T>
void qqbx(const char *s, const H h, T ...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if constexpr(sizeof...(T)) qqbx(++s, args...);
}
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back

using namespace std;
typedef int64_t ll;
const int N = 300025;
const int inf = 1e9;

int n, q;
bool light[N];
map<pair<int,int>,int> last;
/* vector<tuple<int,int,int>> sg; */
struct Segtree {
    struct node {
        node *l, *r;
        int sum;
        node(int s) : sum(s), l(nullptr), r(nullptr) {}
        void pull() {
            sum = 0;
            if(l) sum += l->sum;
            if(r) sum += r->sum;
        }
    } *root = nullptr;
    void add(int p, int d, int l, int r, node *&now) {
        if(l+1 == r) return now = new node(d), void();
        if(!now) now = new node(0);
        int m = l+(r-l)/2;
        if(p < m)
            add(p, d, l, m, now->l);
        else
            add(p, d, m, r, now->r);
        now->pull();
    }
    int query(int ql, int qr, int l, int r, node *now) {
        if(!now || l >= qr || r <= ql) return 0;
        if(ql <= l && r <= qr) return now->sum;
        int m = l+(r-l)/2;
        return query(ql, qr, l, m, now->l) + query(ql, qr, m, r, now->r);
    }
} sgt[N];
void add(int L, int R, int d) {
    /* sg.pb(L, R, d); */
    for(int i = L+1; i < N; i += i&-i) sgt[i].add(R, d, 0, N, sgt[i].root);
}
void toggle(int x, int now) {
    auto &mp = last;
    light[x] = !light[x];
    if(light[x]) {
        int l = x, r = x;
        if(x-1 >= 0 && light[x-1]) {
            auto it = prev(mp.lower_bound({x, 0}));
            auto [L, R] = it->first;
            add(L, R, now - it->second);
            l = L;
            mp.erase(it);
        }
        if(x+1 < n && light[x+1]) {
            auto it = mp.upper_bound({x, inf});
            auto [L, R] = it->first;
            add(L, R, now - it->second);
            r = R;
            mp.erase(it);
        }
        mp[{l, r}] = now;
    } else {
        auto it = prev(mp.upper_bound({x, inf}));
        auto [L, R] = it->first;
        add(L, R, now - it->second);
        mp.erase(it);
        if(L <= x-1) mp[{L, x-1}] = now;
        if(R >= x+1) mp[{x+1, R}] = now;
    }
}
int query(int a, int b, int now) {
    --b;
    int ans = 0;
    {
        if(light[a]) {
            auto it = prev(last.upper_bound({a, inf}));
            auto [l, r] = it->first;
            if(l <= a && b <= r) ans += now - it->second;
        }
    }
    for(int i = a+1; i > 0; i -= i&-i)
        ans += sgt[i].query(b, N, 0, N, sgt[i].root);
    /* for(auto [l, r, d]: sg) { */
    /*     if(l <= a && b <= r) */
    /*         ans += d; */
    /* } */
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> n >> q >> s;
    for(int i = 0; i < n; i++) if(s[i] == '1') toggle(i, 0);
    for(int now = 1; now <= q; now++) {
        char com[7];
        cin >> com;
        if(com[0] == 'q') {
            int a, b;
            cin >> a >> b;
            --a, --b;
            cout << query(a, b, now) << '\n';
        } else if(com[0] == 't') {
            int x;
            cin >> x;
            --x;
            toggle(x, now);
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'Segtree::node::node(int)':
street_lamps.cpp:29:13: warning: 'Segtree::node::sum' will be initialized after [-Wreorder]
         int sum;
             ^~~
street_lamps.cpp:28:15: warning:   'Segtree::node* Segtree::node::l' [-Wreorder]
         node *l, *r;
               ^
street_lamps.cpp:30:9: warning:   when initialized here [-Wreorder]
         node(int s) : sum(s), l(nullptr), r(nullptr) {}
         ^~~~
street_lamps.cpp: In function 'void toggle(int, int)':
street_lamps.cpp:65:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:72:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:80:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [L, R] = it->first;
              ^
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:93:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [l, r] = it->first;
                  ^

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