Submission #257420

#	Time	Username	Problem	Language	Result	Execution time	Memory
257420		2qbingxuan	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	5055 ms	213664 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)) {
        int L = last[rg];
        last.erase(rg);
        auto [l, r] = rg;
        /* vv.pb(rg, (now - L)); */
        DS.add(l, N-1-r, now - L);
    } else {
        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);
    /* for(auto [rg, d]: vv) { */
    /*     auto [l, r] = rg; */
    /*     ++r; */
    /*     if(l <= a && b <= r) ans += d; */
    /* } */
    {
        auto it = prev(lamps.upper_bound(a));
        auto [l, r] = *it;
        if(it->second+1 >= b) {
            /* debug(l, r, a, b); */
            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 addRange(std::pair<int, int>, int, int)':
street_lamps.cpp:42:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [l, r] = rg;
              ^
street_lamps.cpp: In function 'void toggle(int, int)':
street_lamps.cpp:54:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [it, succ] = mp.insert({x, x});
              ^
street_lamps.cpp:54:23: warning: unused variable 'succ' [-Wunused-variable]
         auto [it, succ] = mp.insert({x, x});
                       ^
street_lamps.cpp:73: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: In function 'int query(int, int, int)':
street_lamps.cpp:97:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [l, r] = *it;
              ^
street_lamps.cpp:97:19: warning: unused variable 'l' [-Wunused-variable]
         auto [l, r] = *it;
                   ^
street_lamps.cpp:97:19: 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