Submission #711591

#	Time	Username	Problem	Language	Result	Execution time	Memory
711591		Sanzhar23	Restore Array (RMI19_restore)	C++14	100 / 100	497 ms	1232 KiB

restore

#include <bits/stdc++.h>

using namespace std;

#define ll long long	
#define pb push_back
#define bug cout << "bug" << endl
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pll pair <ll, ll> 
#define pii pair <int, int> 
#define triple pair <pair <ll, ll> , ll>   
#define ull unsigned long long
#define ld long double
#define pinode pair <node*, node*>

const ll INF = 9e18 + 5;
const ll inf = 1e9 + 5;
const ll N = 5e3 + 5;
const ll shift = 2e6;
const ll mod = 998244353;
const ll mod2 = 1e9 + 9;
const ll M = 1e3 + 5;
const ll LOG = 21;
const ll sp = 263;
const ll sp2 = 9973;
const int block = 100;
const double eps = 1e-10;

ll n, m, d[N];
vector <array <ll, 3>> vt; 

int main(){
	speed;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int l, r, k, val;
		cin >> l >> r >> k >> val;
		l++;
		r++;
//		cout << "OGRANI : " << l << " " << r << " " << k << " " << val << endl;
		ll len = r - l + 1;
		if(val == 0){
			vt.pb({l - 1, r, len - k});
		}else{
			vt.pb({r, l - 1, -(len - k + 1)});
		}
	}
	for(int i = 1; i <= n; i++){	
		vt.pb({i - 1, i, 1});
		vt.pb({i, i - 1, 0});
	}
	for(int i = 0; i <= n; i++){
		vt.pb({n + 1, i, 0});
	}
	for(int i = 0; i <= n + 1; i++){
		d[i] = INF;
	}
	d[n + 1] = 0;
	for(int col = 0; col <= n; col++){
		for(int i = 0; i < vt.size(); i++){
			ll a = vt[i][0], b = vt[i][1], w = vt[i][2];
			if(d[a] < INF){
				if(d[b] > d[a] + w){
					d[b] = max(-INF, d[a] + w);
				}
			}
		}
	}
	bool cycle = false;
	for(int i = 0; i < vt.size(); i++){
		ll a = vt[i][0], b = vt[i][1], w = vt[i][2];
		if(d[a] < INF){
			if(d[b] > d[a] + w){
				cycle = true;
				break;
			}
		}
		if(cycle)
			break;
	}
	if(cycle){
		cout << -1 << endl;
		return 0;
	}
	for(int i = 1; i <= n; i++){
		cout << d[i] - d[i - 1] << " ";
	}
}
/*		
%I64d6


7 7
0 2 1 0
0 6 1 0
0 1 1 0
1 1 1 1
6 6 1 1
3 6 1 1
2 4 1 1



0 1 1 1 1 1 1
		



%I64d
*/ 

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i < vt.size(); i++){
      |                  ~~^~~~~~~~~~~
restore.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0; i < vt.size(); i++){
      |                 ~~^~~~~~~~~~~

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