Submission #258144

#	Time	Username	Problem	Language	Result	Execution time	Memory
258144		oolimry	Restore Array (RMI19_restore)	C++14	0 / 100	5 ms	640 KiB

restore

#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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55