Submission #257425

#	Time	Username	Problem	Language	Result	Execution time	Memory
257425		2qbingxuan	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	5098 ms	8588 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;

int n, q;
bool light[N];
vector<pair<pair<int,int>,int>> vv;
/* struct JIZZZZZ { */
/*     unordered_map<int,int> sum[N]; */
/*     void add(int x, int y, int d) { */
/*         ++x, ++y; */
/*         for(int i = x; i < N; i += i&-i) for(int j = y; j < N; j += j&-j) sum[i][j] += d; */
/*     } */
/*     int query(int x, int y) { */
/*         ++x, ++y; */
/*         int res = 0; */
/*         for(int i = x; i > 0; i -= i&-i) for(int j = y; j > 0; j -= j&-j) if(sum[i].count(j)) res += sum[i][j]; */
/*         return res; */
/*     } */
/* } DS; */
map<pair<int,int>,int> last;
void addRange(pair<int,int> rg, int d, int now) {
    if(last.count(rg)) {
        assert(d == -1);
        int L = last[rg];
        last.erase(rg);
        vv.pb(rg, now - L);
        /* auto [l, r] = rg; */
        /* DS.add(l, N-1-r, now - L); */
    } else {
        assert(d == 1);
        last[rg] = now;
    }
}
map<int,int> lamps;
void toggle(int x, int now) {
    map<int,int> &mp = lamps;
    if(!light[x]) {
        light[x] = true;
        auto [it, succ] = mp.insert({x, x});
        assert(succ);
        if(next(it) != mp.end() && next(it)->first == x+1) {
            it->second = next(it)->second;
            addRange(*next(it), -1, now);
            mp.erase(next(it));
        }
        if(it != mp.begin() && prev(it)->second == x-1) {
            addRange(*prev(it), -1, now);
            prev(it)->second = it->second;
            mp.erase(it--);
        }
        addRange(*it, 1, now);
    } else {
        light[x] = false;
        auto it = prev(mp.upper_bound(x));
        addRange(*it, -1, now);
        assert(it->first <= x && x <= it->second);
        if(it->second >= x+1) {
            auto [jt, succ] = mp.insert({x+1, it->second});
            assert(succ);
            addRange(*jt, 1, now);
        }
        if(it->first <= x-1) {
            it->second = x-1;
            addRange(*it, 1, now);
        } else {
            mp.erase(it);
        }
    }
    debug(x);
    for(auto [l, r]: mp) cerr << l << ' ' << r << '\n';
    debug(mp.size());
}
int query(int a, int b, int now) {
    /* int ans = DS.query(a, N-b); */
    int ans = 0;
    for(auto [rg, d]: vv) {
        auto [l, r] = rg;
        ++r;
        if(l <= a && b <= r) ans += d;
    }
    {
        auto it = prev(lamps.upper_bound(a));
        if(it->second+1 >= b) {
            auto [l, r] = *it;
            /* debug(l, r, a, b); */
            assert(last.count(*it));
            int L = last[*it];
            ans += now - L;
        }
    }
    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 function 'void toggle(int, int)':
street_lamps.cpp:56:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [it, succ] = mp.insert({x, x});
              ^
street_lamps.cpp:75:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [jt, succ] = mp.insert({x+1, it->second});
                  ^
street_lamps.cpp:87:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [l, r]: mp) cerr << l << ' ' << r << '\n';
              ^
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:93:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [rg, d]: vv) {
              ^
street_lamps.cpp:94:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [l, r] = rg;
              ^
street_lamps.cpp:101:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [l, r] = *it;
                  ^
street_lamps.cpp:101:23: warning: unused variable 'l' [-Wunused-variable]
             auto [l, r] = *it;
                       ^
street_lamps.cpp:101:23: warning: unused variable 'r' [-Wunused-variable]

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