oj.uz

Submission #711520

# Submission time Handle Problem Language Result Execution time Memory
711520 2023-03-17T07:08:51 Z Sanzhar23 Restore Array (RMI19_restore) C++14
0 / 100
 104 ms 1360 KB 
#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++;
		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++){
		d[i] = INF;
	}
	d[0] = 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

restore.cpp: In function 'int main()':
restore.cpp:59: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]
   59 |   for(int i = 0; i < vt.size(); i++){
      |                  ~~^~~~~~~~~~~
restore.cpp:69: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]
   69 |  for(int i = 0; i < vt.size(); i++){
      |                 ~~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1360 KB Output is correct
2 Correct 96 ms 1348 KB Output is correct
3 Correct 95 ms 1360 KB Output is correct
4 Incorrect 100 ms 1360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1360 KB Output is correct
2 Correct 96 ms 1348 KB Output is correct
3 Correct 95 ms 1360 KB Output is correct
4 Incorrect 100 ms 1360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -