Submission #257730

#	Time	Username	Problem	Language	Result	Execution time	Memory
257730		2qbingxuan	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	3 ms	640 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];
map<pair<int,int>,int> last;
vector<tuple<int,int,int>> sg;
void add(int L, int R, int d) {
    sg.pb(L, R, d);
}
void toggle(int x, int now) {
    auto &mp = last;
    light[x] = !light[x];
    if(light[x]) {
        int l = x, r = x;
        if(x > 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 < n-1 && light[x+1]) {
            auto it = mp.upper_bound({x, 0});
            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, 0}));
        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;
    {
        auto it = prev(last.upper_bound({a, 0}));
        auto [l, r] = it->first;
        if(l <= a && b <= r) ans += now - it->second;
    }
    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 function 'void toggle(int, int)':
street_lamps.cpp:35:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:42:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
             auto [L, R] = it->first;
                  ^
street_lamps.cpp:50: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:62:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [l, r] = it->first;
              ^
street_lamps.cpp:65:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [l, r, d]: sg) {
              ^

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