Submission #551375

#	Time	Username	Problem	Language	Result	Execution time	Memory
551375		ala2	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	2025 ms	228784 KiB

street_lamps

    #include <bits/stdc++.h>
    using namespace std;
    #define vi vector<int>
    #define all(X) begin(X), end(X)
     
    struct BIT {
    	vector<int> a; int n, sum = 0;
     
    	BIT(int N) : a((n=N)+1) {}
     
    	void add(int i, int v) {
    		sum += v;
    		for(++i; i <= n; i += i&-i) a[i] += v;
    	}
    	int get(int i) {
    		int v = 0;
    		for(++i; i >= 1; i -= i&-i) v += a[i];
    		return v;
    	}
    	int suf(int i) { // [i...)
    		return sum - get(i-1); }
    };
     
    const int Z = 3e5+1;
     
    int lg[Z+1];
     
    int lowerB(const vi &a, const int &v) {
    	int i = -1;
    	for(int j = lg[size(a)]; j/= 2; )
    		if(i+j < size(a) && a[i+j] < v) i += j;
    	return i + 1;
    }
     
    struct CompoundBIT {
    	int n;
    	vector<vi> a;
    	vector<BIT*> b;
     
    	CompoundBIT(int N) : n(N), a(N), b(N) {}
     
    	void addVal(int i, int v) {
    		for(++i; i < n; i += i&-i) a[i].push_back(v);
    	}
    	void build() {
    		for(int i = 1; i < n; i++) {
    			sort(all(a[i]));
    			b[i] = new BIT(size(a[i]));
    		}
    	}
    	void update(int i, int v, int w) {
    		for(++i; i < n; i += i&-i) 
    			b[i]->add(lowerB(a[i], v), w);
    	}
    	int query(int i, int v) {
    		int x = 0;
    		for(++i; i > 0; i -= i&-i)
    			x += b[i]->suf(lowerB(a[i], v));
    		return x;
    	}
    } cb(Z);
     
    int N, Q;
    string _inp;
     
    int qL[Z], qR[Z];
    bitset<Z> qType, state;
     
    set<array<int, 2>> intervals;
    vector<array<int, 3>> iAt[Z];
    array<int, 2> iFound[Z];
    map<int, int> last[Z];
     
    void addInterval(int l, int r, int i) {
    	if(r < l) return;
    	cb.addVal(l, r);
    	intervals.insert({l, r});
    	iAt[i].push_back({l, r, 1});
    }
     
    void remInterval(int l, int r, int i) {
    	if(r < l) return;
    	intervals.erase({l, r});
    	iAt[i].push_back({l, r, 0});
    }
     
    int main() {
    	ios::sync_with_stdio(0), cin.tie(0);
     
    	for(int i=0; i<=Z; ++i)
    		lg[i] = 2<<__lg(i);
     
     	cin >> N >> Q;
    	cin >> _inp;
     
    	for(int i = 0; i < N; ++i)
    		state[i] = _inp[i] - '0';
     
    	for(int i = 0; i < N; ++i) if(state[i]) {
    		int l = i;
    		while(i < N && state[i]) ++i;
    		addInterval(l, i-1, 0);
    	}
     
    	for(int i = 1; i <= Q; ++i) {
    		cin >> _inp >> qL[i]; --qL[i];
     
    		if((qType[i] = _inp[0] == 'q')) {
    			cin >> qR[i];
    			qR[i] -= 2;
    			auto f = intervals.upper_bound({qL[i], Z});
    			if(!empty(intervals) && f != begin(intervals))
    				iFound[i] = *--f;
    			else
    				iFound[i][0] = Z;
    		} else {
    			auto f = intervals.upper_bound({qL[i], Z});
    			int v = qL[i];
    			if(state[v]) {
    				auto [l, r] = *--f;
    				remInterval(l, r, i);
    				addInterval(l, v-1, i);
    				addInterval(v+1, r, i);
    			} else {
    				int l = v, r = v;
    				if(v + 1 < N && state[v+1]) r = (*f)[1];
    				if(v + 0 > 0 && state[v-1]) l = (*--f)[0];
    				remInterval(v+1, r, i);
    				remInterval(l, v-1, i);
    				addInterval(l, r, i);
    			}
    			state[v] = !state[v];
    		}
    	}
    	cb.build();
     
    	for(int i = 0; i <= Q; ++i) {
    		for(auto &[l, r, toAdd] : iAt[i]) {
    			if(toAdd) last[l][r] = i;
    			else cb.update(l, r, i - last[l][r]);
    		}
    		if(qType[i]) {
    			int res = cb.query(qL[i], qR[i]);
    			auto [l, r] = iFound[i];
    			if(l <= qL[i] && qR[i] <= r)
    				res += i - last[l][r];
    			cout << res << '\n';
    		}
    	}
    }

Compilation message (stderr)

street_lamps.cpp: In function 'int lowerB(const std::vector<int>&, const int&)':
street_lamps.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       if(i+j < size(a) && a[i+j] < v) i += j;
      |          ~~~~^~~~~~~~~

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