oj.uz

Submission #154728

# Submission time Handle Problem Language Result Execution time Memory
154728 2019-09-24T09:08:11 Z Pro_ktmr Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 18136 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

//RMQ RUQ
struct SegmentTree{
private:
    int N;
    vector<long long> node, lazy;
    vector<bool> lazyFlg;
public:
    void init(int n){
        N = 1;
        while(N < n) N *= 2;
        node.clear();
        lazy.clear();
        lazyFlg.clear();
        for(int i=0; i<N*2-1; i++){
            node.push_back(LLONG_MAX);
            lazy.push_back(0);
            lazyFlg.push_back(false);
        }
    }
    void eval(int k, int l, int r){
        if(lazyFlg[k] == false) return;
        node[k] = lazy[k];
        lazyFlg[k] = false;
        if(r-l > 1){
            lazy[2*k+1] = lazy[k];
            lazyFlg[2*k+1] = true;
            lazy[2*k+2] = lazy[k];
            lazyFlg[2*k+2] = true;
        }
    }
    void update(int a, int b, long long x, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k, l, r);
        if(r <= a || b <= l) return;
        if(a <= l && r <= b){
            lazy[k] = x;
            lazyFlg[k] = true;
            eval(k, l, r);
        }
        else{
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }
    long long query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k, l, r);
        if(r <= a || b <= l) return LLONG_MAX;
        if(a <= l && r <= b) return node[k];
        else return min(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r));
    }
};

int N,Q;
string def;
int t[300000],a[300000],b[300000];
SegmentTree st;

int main(){
	cin >> N >> Q;
	cin >> def;
	for(int i=0; i<Q; i++){
		string type;
		cin >> type;
		if(type == "toggle"){
			t[i] = 0;
			cin >> a[i];
			a[i]--;
		}
		else{
			t[i] = 1;
			cin >> a[i] >> b[i];
			a[i]--; b[i]--;
			st.init(N);
			for(int j=0; j<N; j++){
				st.update(j, j+1, def[j]-'0');
			}
			int ans = 0;
			for(int j=0; j<=i; j++){
				if(st.query(a[i], b[i]) == 1) ans++;
				if(t[j] == 0) st.update(a[j], a[j]+1, st.query(a[j], a[j]+1)^1);
			}
			cout << ans << endl;
		}
	}
	
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 129 ms 376 KB Output is correct
3 Correct 218 ms 480 KB Output is correct
4 Correct 286 ms 376 KB Output is correct
5 Execution timed out 5095 ms 18136 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 464 KB Output is correct
2 Correct 317 ms 464 KB Output is correct
3 Correct 220 ms 376 KB Output is correct
4 Correct 18 ms 348 KB Output is correct
5 Execution timed out 5080 ms 18032 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Execution timed out 5042 ms 996 KB Time limit exceeded
9 Halted 0 ms 0 KB -