oj.uz

Submission #258152

# Submission time Handle Problem Language Result Execution time Memory
258152 2020-08-05T12:46:33 Z oolimry Restore Array (RMI19_restore) C++14
13 / 100
 8 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;
			l++;
		}
		if(r&1){
			r--;
			tree[r] |= x;
		}
	}
}

void update2(int i, int x){
	for(i += n;i;i >>= 1) tree[i] |= 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;i < 2*n;i++){
		tree[i] |= tree[i>>1];
	}
	
	for(int i = 0;i < n;i++){
		if(tree[i+n] == 0) update2(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 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Incorrect 4 ms 512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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