Submission #538441

#	Time	Username	Problem	Language	Result	Execution time	Memory
538441		Evang	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	933 ms	71532 KiB

street_lamps

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


using vup = vc<array<int, 3>>;
const int N = 3e5+5;
const int Q = N;
int n, q, ans[Q];
bitset<Q> t;

template<typename T>
struct BIT {
    T bit[N]{};
    vc<pair<int, T>> un;

    void _upd(int i, T x){
        while(i<=n+2){
            bit[i] += x;
            i += i&-i;
        }
    }
    void upd(int i, T x){
        un.eb(i, x);
        _upd(i, x);
    }
    T sum(int r){
        T s = 0;
        while(r>0){
            s += bit[r];
            r -= r&-r;
        }
        return s;
    }
    T qry(int l, int r){
        return sum(r) - sum(l-1);
    }
    void clear(){
        while(!un.empty()){
            auto[i, x] = un.back();
            un.pop_back();
            _upd(i, -x);
        }
    }
};

BIT<int> bit, a;

void cdq(vup &e, int l, int r){
    if(l==r)
        return;
    int m = (l+r)/2;
    cdq(e, l, m);
    cdq(e, m+1, r);

    bit.clear();
    int j = l;
    for(int i = m+1; i <= r; ++i){
        if(t[abs(e[i][0])]==0)
            continue;

        while(j<=m && (t[abs(e[j][0])]==1 || e[j][1] <= e[i][1])){
            if(t[abs(e[j][0])]==0)
                bit.upd(e[j][2], e[j][0]);
            ++j;
        }
        ans[e[i][0]] += bit.qry(1, e[i][2]);
    }

    vup res;
    j = l;
    int i = m+1;
    while(j<=m || i <= r){
        if(j>m||i<=r&&e[i][1]<e[j][1])
            res.pb(e[i++]);
        else
            res.pb(e[j++]);
    }
    for(i = l; i <= r; ++i)
        e[i] = res[i-l];
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        char c;
        cin >> c;
        if(c=='1')
            a.upd(i, 1);
    }

    vup e;
    for(int i = 1; i <= q; ++i){
        str o;
        cin >> o;
        if(o=="toggle"){
            int j;
            cin >> j;
            int l = j, r = j;
            for(int u = n; u > 0; u /= 2){
                while(l-u>0&&a.qry(l-u, j-1)==j-(l-u))
                    l -= u;
                while(r+u<=n&&a.qry(j+1, r+u)==r+u-j)
                    r += u;
            }

            if(a.qry(j, j)==1){
                e.pb(array<int, 3>{i, j+1, r+1});
                e.pb(array<int, 3>{i, l, j});
                e.pb(array<int, 3>{-i, j+1, j});
                e.pb(array<int, 3>{-i, l, r+1});
                a.upd(j, -1);
            }else{
                e.pb(array<int, 3>{-i, j+1, r+1});
                e.pb(array<int, 3>{-i, l, j});
                e.pb(array<int, 3>{i, j+1, j});
                e.pb(array<int, 3>{i, l, r+1});
                a.upd(j, 1);
            }
        }else{
            t[i] = 1;
            int l, r;
            cin >> l >> r;
            --r;
            e.pb(array<int, 3>{i, l, r});
            if(a.qry(l, r)==r-l+1)
                ans[i] = i;
        }
    }

    cdq(e, 0, ssize(e)-1);

    for(int i = 1; i <= q; ++i)
        if(t[i])
            cout << ans[i] << el;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void cdq(vup&, int, int)':
street_lamps.cpp:130:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  130 |         if(j>m||i<=r&&e[i][1]<e[j][1])

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