oj.uz

Submission #258145

# Submission time Handle Problem Language Result Execution time Memory
258145 2020-08-05T12:35:58 Z oolimry Restore Array (RMI19_restore) C++14
0 / 100
 3 ms 640 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;

vector<ii> ones;
vector<ii> zeros;

int n, Q; 
int tree[100005];

void update(int l, int r, int x){
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1) tree[l++] |= x;
		if(r&1) tree[--r] |= x;
	}
}

int query(int l, int r){
	int res = 0;
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1) res |= tree[l++];
		if(r&1) res |= tree[--r];
	}
	return res;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> Q;
	while(Q--){
		int l, r, k, x; cin >> l >> r >> k >> x;
	
		if(k == 1){
			if(x == 1){
				update(l,r+1,x+1);
			}
			else zeros.push_back(ii(l,r));
		}
		else{
			if(x == 0){
				update(l,r+1,x+1);
			}	
			else ones.push_back(ii(l,r));
		}
	}
	
	for(int i = 2*n;i >= 2;i--){
		tree[i] |= tree[i>>1];
	}
	
	for(ii x : ones){
		int l = x.first, r = x.second;
		if((query(l,r+1) & 2) == 0){
			cout << -1;
			return 0;
		}
	}
	
	for(ii x : zeros){
		int l = x.first, r = x.second;
		
		if((query(l,r+1) & 1) == 0){
			cout << -1;
			return 0;
		}
	}
	
	for(int i = 0;i < n;i++){
		if(tree[i+n] == 3){
			cout << -1;
			return 0;
		}
	}
	
	for(int i = 0;i < n;i++){
		cout << max(0, tree[i+n]-1) << " ";
	}
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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