oj.uz

Submission #551375

# Submission time Handle Problem Language Result Execution time Memory
551375 2022-04-20T14:16:36 Z ala2 Street Lamps (APIO19_street_lamps) C++17
60 / 100
 2025 ms 228784 KB 
    #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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55436 KB Output is correct
2 Correct 37 ms 55512 KB Output is correct
3 Correct 40 ms 55496 KB Output is correct
4 Correct 40 ms 55500 KB Output is correct
5 Correct 36 ms 55472 KB Output is correct
6 Correct 36 ms 55464 KB Output is correct
7 Correct 36 ms 55452 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 86060 KB Output is correct
2 Correct 1603 ms 86532 KB Output is correct
3 Correct 1713 ms 85840 KB Output is correct
4 Correct 1529 ms 103952 KB Output is correct
5 Correct 1498 ms 98060 KB Output is correct
6 Correct 1642 ms 105940 KB Output is correct
7 Correct 192 ms 62164 KB Output is correct
8 Correct 217 ms 63520 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 55756 KB Output is correct
2 Correct 40 ms 55704 KB Output is correct
3 Correct 39 ms 55612 KB Output is correct
4 Correct 41 ms 55536 KB Output is correct
5 Correct 2025 ms 115492 KB Output is correct
6 Correct 1817 ms 108888 KB Output is correct
7 Correct 1368 ms 96372 KB Output is correct
8 Correct 209 ms 62516 KB Output is correct
9 Correct 113 ms 60236 KB Output is correct
10 Correct 129 ms 60520 KB Output is correct
11 Correct 166 ms 60652 KB Output is correct
12 Correct 182 ms 61060 KB Output is correct
13 Correct 197 ms 62452 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 55596 KB Output is correct
2 Correct 38 ms 55628 KB Output is correct
3 Correct 41 ms 55668 KB Output is correct
4 Correct 41 ms 55756 KB Output is correct
5 Correct 642 ms 80136 KB Output is correct
6 Correct 1034 ms 94196 KB Output is correct
7 Correct 1598 ms 105328 KB Output is correct
8 Runtime error 936 ms 228784 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55436 KB Output is correct
2 Correct 37 ms 55512 KB Output is correct
3 Correct 40 ms 55496 KB Output is correct
4 Correct 40 ms 55500 KB Output is correct
5 Correct 36 ms 55472 KB Output is correct
6 Correct 36 ms 55464 KB Output is correct
7 Correct 36 ms 55452 KB Output is correct
8 Correct 1444 ms 86060 KB Output is correct
9 Correct 1603 ms 86532 KB Output is correct
10 Correct 1713 ms 85840 KB Output is correct
11 Correct 1529 ms 103952 KB Output is correct
12 Correct 1498 ms 98060 KB Output is correct
13 Correct 1642 ms 105940 KB Output is correct
14 Correct 192 ms 62164 KB Output is correct
15 Correct 217 ms 63520 KB Output is correct
16 Correct 38 ms 55756 KB Output is correct
17 Correct 40 ms 55704 KB Output is correct
18 Correct 39 ms 55612 KB Output is correct
19 Correct 41 ms 55536 KB Output is correct
20 Correct 2025 ms 115492 KB Output is correct
21 Correct 1817 ms 108888 KB Output is correct
22 Correct 1368 ms 96372 KB Output is correct
23 Correct 209 ms 62516 KB Output is correct
24 Correct 113 ms 60236 KB Output is correct
25 Correct 129 ms 60520 KB Output is correct
26 Correct 166 ms 60652 KB Output is correct
27 Correct 182 ms 61060 KB Output is correct
28 Correct 197 ms 62452 KB Output is correct
29 Correct 42 ms 55596 KB Output is correct
30 Correct 38 ms 55628 KB Output is correct
31 Correct 41 ms 55668 KB Output is correct
32 Correct 41 ms 55756 KB Output is correct
33 Correct 642 ms 80136 KB Output is correct
34 Correct 1034 ms 94196 KB Output is correct
35 Correct 1598 ms 105328 KB Output is correct
36 Runtime error 936 ms 228784 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -