Submission #218011

#	Time	Username	Problem	Language	Result	Execution time	Memory
218011		tincamatei	Restore Array (RMI19_restore)	C++14	100 / 100	444 ms	5120 KiB

restore

/**
* user:  tinca-6db
* fname: Matei
* lname: Tinca
* task:  restore
* score: 100.0
* date:  2019-10-10 08:18:43.220236
*/
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5000;

struct Edge {
	int son, difa, difb;
};

struct Range {
	int l, r;
} range[1+MAX_N];

vector<Edge> graph[1+MAX_N];

void reportError() {
	printf("-1");
	exit(0);
}

bool ok;
void dfs(int nod) {
	for(auto it: graph[nod]) {
		int newL = range[nod].l + it.difa, newR = range[nod].r + it.difb;
		if(newL > range[it.son].l || newR < range[it.son].r) {
			range[it.son].l = max(range[it.son].l, newL);
			range[it.son].r = min(range[it.son].r, newR);
			if(range[it.son].l > range[it.son].r)
				reportError();
			ok = true;
			dfs(it.son);
		}
	}
}

void insertLessStrict(int a, int b, int k) {
	graph[a].push_back({b, -MAX_N, k - 1});
	graph[b].push_back({a, -(k - 1), MAX_N});
}

void insertGreaterEq(int a, int b, int k) {
	graph[a].push_back({b, k, MAX_N});
	graph[b].push_back({a, -MAX_N, -k});
}

int main() {
	int N, M;
	int l, r, k, val;
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; ++i) {
		scanf("%d%d%d%d", &l, &r, &k, &val);
		++l;
		++r;
		
		if(val == 0) {
			insertGreaterEq(l - 1, r, k);
		} else {
			insertLessStrict(l - 1, r, k);
		}
	}

	for(int i = 0; i < N; ++i) {
		insertGreaterEq(i, i + 1, 0);
		insertLessStrict(i, i + 1, 2);
	}

	for(int i = 0; i <= N; ++i)
		range[i] = {0, i};
	
	do {
		ok = false;
		for(int i = 0; i <= N; ++i)
			dfs(i);
	} while(ok);

	for(int i = 1; i <= N; ++i)
		printf("%d ", 1 ^ (range[i].l - range[i - 1].l));

	return 0;
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
restore.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &l, &r, &k, &val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55