Submission #1014345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014345		idiotcomputer	Restore Array (RMI19_restore)	C++11	100 / 100	211 ms	1088 KiB

restore

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define sz size 

const int inf = 1e8;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin >> n >> m;

	n++;
	vector<pii> adj[n];
	for (int i =0; i < n-1; i++) adj[i].pb((pii) {i+1,1});
	for (int i = 1; i < n; i++) adj[i].pb((pii) {i-1,0});

	int l,r,k,v;
	for (int i = 0; i < m; i++){
		cin >> l >> r >> k >> v;
		r++;
		if (v == 0) adj[r].pb((pii) {l,-k});
		else adj[l].pb((pii) {r,k-1});
	}

	int d[n];
	for (int i =0; i < n; i++) d[i] = inf;
	d[0] = 0;
	for (int i =0; i < n-1; i++){
		for (int j =0; j < n; j++){
			for (pii c : adj[j]) d[c.f] = min(d[c.f], d[j]+c.s);
		}
	}

	bool f = false;
	for (int i = 0; i < n; i++){
		for (pii c : adj[i]) if (d[c.f] > d[i]+c.s){ f = true; break;}
	}
	if (f){ cout << "-1\n"; return 0;}

	for (int i = 1; i < n; i++){
		if (d[i] > d[i-1]) cout << "0 ";
		else cout << "1 ";
	}
	cout << "\n";
}

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