Submission #1127758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127758		Double_Slash	Street Lamps (APIO19_street_lamps)	C++20	Compilation error	0 ms	0 KiB

street_lamps

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

template <class T>
struct Cc : vector<T> {
    using vector<T>::begin, vector<T>::end, vector<T>::erase;

    void init() {
        sort(begin(), end());
        erase(unique(begin(), end()), end());
    }

    int inc(const T &t) { return lower_bound(begin(), end(), t) - begin(); }

    int exc(const T &t) { return upper_bound(begin(), end(), t) - begin(); }
};

struct St2 {
    int n;
    Cc<int> cc;
    vector<int> st;

    void add(int i) { cc.emplace_back(i); }

    void init() {
        cc.init();
        n = cc.size();
        st.resize(n << 1);
    }

    void update(int l, int r, int v) {
        for (l = cc.inc(l) + n, r = cc.exc(r) + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) st[l++] += v;
            if (r & 1) st[--r] += v;
        }
    }

    int query(int i) {
        int ret = 0;
        for (i = cc.inc(i) + n; i; i >>= 1) ret += st[i];
        return ret;
    }
};

struct St {
    int n;
    vector<St2> st;

    St(int n) : n(n), st(n << 1) {}

    void add(int i, int j) { for (i += n; i; i >>= 1) st[i].add(j); }

    void init() { for (int i = n << 1; --i;) st[i].init(); }

    void update(int l, int r, int l2, int r2, int v) {
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) st[l++].update(l2, r2, v);
            if (r & 1) st[--r].update(l2, r2, v);
        }
    }

    int query(int i, int j) {
        int ret = 0;
        for (i += n; i; i >>= 1) ret += st[i].query(j);
        return ret;
    }
};

int n, q, a[300000], b[300000];
bool on[300000];
map<int, pint> ranges;

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        on[i] = c == '1';
        if (on[i]) {
            if (ranges.empty() or ranges.rbegin()->second.first < i - 1) ranges[i] = {i, -1};
            else ranges.rbegin()->second.first = i;
        }
    }
    St st{n};
    for (int i = 0; i < q; ++i) {
        string s;
        cin >> s >> a[i];
        a[i]--;
        if (s[0] == 't') b[i] = -1;
        else {
            cin >> b[i];
            st.add(a[i], b[i] -= 2);
        }
    }
    st.init();
    for (int i = 0; i < q; ++i) {
        auto rem = [&] (int l) {
            auto [r, t] = ranges[l];
            st.update(l, n, 0, r, i - t);
            ranges.erase(l);
        };
        if (~b[i]) {
            int ans = st.query(a[i], b[i]);
            auto it = ranges.upper_bound(a[i]);
            if (it != ranges.begin() and (--it)->second.first >= b[i]) ans += i - it->second.second;
            cout << ans << '\n';
        } else if (on[a[i]]) {
            on[a[i]] = false;
            int l = prev(ranges.upper_bound(a[i]))->first;
            int r = ranges[l].first;
            rem(l);
            if (l < a[i]) ranges[l] = {a[i] - 1, i};
            if (a[i] < r) ranges[a[i] + 1] = {r, i};
        } else {
            on[a[i]] = true;
            int l = a[i], r = a[i];
            auto it = ranges.upper_bound(r);
            if (it != ranges.end() and it->first == r + 1) {
                r = it++->second.first;
                rem(a[i] + 1);
            }
            if (it != ranges.begin() and (--it)->second.first == l - 1) rem(l = it->first);
            ranges[l] = {r, i};
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:82:17: error: reference to 'ranges' is ambiguous
   82 |             if (ranges.empty() or ranges.rbegin()->second.first < i - 1) ranges[i] = {i, -1};
      |                 ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:82:35: error: reference to 'ranges' is ambiguous
   82 |             if (ranges.empty() or ranges.rbegin()->second.first < i - 1) ranges[i] = {i, -1};
      |                                   ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:82:74: error: reference to 'ranges' is ambiguous
   82 |             if (ranges.empty() or ranges.rbegin()->second.first < i - 1) ranges[i] = {i, -1};
      |                                                                          ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:83:18: error: reference to 'ranges' is ambiguous
   83 |             else ranges.rbegin()->second.first = i;
      |                  ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp: In lambda function:
street_lamps.cpp:100:27: error: reference to 'ranges' is ambiguous
  100 |             auto [r, t] = ranges[l];
      |                           ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:102:13: error: reference to 'ranges' is ambiguous
  102 |             ranges.erase(l);
      |             ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:106:23: error: reference to 'ranges' is ambiguous
  106 |             auto it = ranges.upper_bound(a[i]);
      |                       ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:107:23: error: reference to 'ranges' is ambiguous
  107 |             if (it != ranges.begin() and (--it)->second.first >= b[i]) ans += i - it->second.second;
      |                       ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:111:26: error: reference to 'ranges' is ambiguous
  111 |             int l = prev(ranges.upper_bound(a[i]))->first;
      |                          ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:112:21: error: reference to 'ranges' is ambiguous
  112 |             int r = ranges[l].first;
      |                     ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:114:27: error: reference to 'ranges' is ambiguous
  114 |             if (l < a[i]) ranges[l] = {a[i] - 1, i};
      |                           ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:115:27: error: reference to 'ranges' is ambiguous
  115 |             if (a[i] < r) ranges[a[i] + 1] = {r, i};
      |                           ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:119:23: error: reference to 'ranges' is ambiguous
  119 |             auto it = ranges.upper_bound(r);
      |                       ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:120:23: error: reference to 'ranges' is ambiguous
  120 |             if (it != ranges.end() and it->first == r + 1) {
      |                       ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:124:23: error: reference to 'ranges' is ambiguous
  124 |             if (it != ranges.begin() and (--it)->second.first == l - 1) rem(l = it->first);
      |                       ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~
street_lamps.cpp:125:13: error: reference to 'ranges' is ambiguous
  125 |             ranges[l] = {r, i};
      |             ^~~~~~
In file included from /usr/include/c++/11/compare:39,
                 from /usr/include/c++/11/bits/stl_pair.h:65,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from street_lamps.cpp:1:
/usr/include/c++/11/concepts:163:13: note: candidates are: 'namespace std::ranges { }'
  163 |   namespace ranges
      |             ^~~~~~
street_lamps.cpp:73:16: note:                 'std::map<int, std::pair<int, int> > ranges'
   73 | map<int, pint> ranges;
      |                ^~~~~~