oj.uz

Submission #154730

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

//RMaxQ 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(1000000000);
            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] = max(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 -1;
        if(a <= l && r <= b) return node[k];
        else return max(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;
	st.init(N);
	cin >> def;
	for(int i=0; i<N; i++){
		if(def[i] == '1') st.update(i, i+1, 0);
	}
	for(int i=0; i<Q; i++){
		string type;
		cin >> type;
		if(type == "toggle"){
			t[i] = 0;
			cin >> a[i];
			a[i]--;
			st.update(a[i], a[i]+1, i+1);
		}
		else{
			t[i] = 1;
			cin >> a[i] >> b[i];
			a[i]--; b[i]--;
			int tmp = st.query(a[i], b[i]);
			if(tmp == 1000000000) cout << 0 << endl;
			else cout << i+1 - tmp << endl;
		}
	}
	
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 755 ms 4872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 7 ms 348 KB Output is correct
5 Correct 574 ms 25220 KB Output is correct
6 Correct 914 ms 26288 KB Output is correct
7 Correct 1254 ms 27056 KB Output is correct
8 Correct 1691 ms 29140 KB Output is correct
9 Correct 975 ms 6936 KB Output is correct
10 Correct 1066 ms 7424 KB Output is correct
11 Correct 1064 ms 7572 KB Output is correct
12 Correct 1615 ms 27812 KB Output is correct
13 Correct 1709 ms 29232 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Incorrect 6 ms 420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -