oj.uz

답안 #154730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154730 2019-09-24T09:08:36 Z Pro_ktmr 가로등 (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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 755 ms 4872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -