oj.uz

답안 #659508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659508 2022-11-18T10:31:08 Z franfill Restore Array (RMI19_restore) C++17
13 / 100
 126 ms 196044 KB 
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector < vector < int > > greater(n, vector < int > (n+1, 0));
	vector < vector < int > > smaller(n, vector < int > (n+1, n));

	for (int i = 0; i < m; i++)
	{
		int l, r, k, value;
		cin >> l >> r >> k >> value;
		r++;
		int len = r-l;
		if (value == 0)
			smaller[l][r] = min(smaller[l][r], len - k);
		else
			greater[l][r] = max(greater[l][r], len - k + 1);
	}
	for (int i = 0; i < n; i++)
		smaller[i][i+1] = min(smaller[i][i+1], 1);

/*
	for (int i = 0; i < n; i++)
		for (int j = i+1; j <= n; j++)
			cerr << i << " -> " << j << " " << smaller[i][j] << " " << greater[i][j] << "\n";
	*/

	vector < int > mi(n+1, 0);
	vector < int > ma(n+1, n);
	ma[0] = 0;
	for (int i = 0; i < n; i++)
	{
		int res = 0;
		for (int j = n; j > i; j--)
		{
			res = max(res, greater[i][j]);
			mi[j] = max(mi[j], mi[i] + res);
			ma[j] = min(ma[j], ma[i] + smaller[i][j]);
			res = max(res-1, 0);
		}
		if (res != 0)
		{
			cout << -1 << "\n";
			return 0;
		}
	}

	for (int i = 0; i < n; i++)
		for (int j = i+1; j <= n; j++)
		{
			assert(ma[j] <= ma[i] + smaller[i][j]);
		}

	vector < int > res;
	for (int i = 1; i <= n; i++)
	{
		if (mi[i] > ma[i])
		{
			cout << -1 << "\n";
			return 0;
		}
		res.emplace_back(mi[i] - mi[i-1]);
		//assert(res.back() == 1 || res.back() == 0);
	}
	for (auto x : res)
		cout << x << " ";
	cout << "\n";
	return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 195808 KB Output is correct
2 Correct 117 ms 192652 KB Output is correct
3 Correct 121 ms 196044 KB Output is correct
4 Correct 120 ms 191600 KB Output is correct
5 Correct 120 ms 190460 KB Output is correct
6 Correct 117 ms 195796 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 195808 KB Output is correct
2 Correct 117 ms 192652 KB Output is correct
3 Correct 121 ms 196044 KB Output is correct
4 Correct 120 ms 191600 KB Output is correct
5 Correct 120 ms 190460 KB Output is correct
6 Correct 117 ms 195796 KB Output is correct
7 Correct 118 ms 191660 KB Output is correct
8 Correct 119 ms 192396 KB Output is correct
9 Incorrect 126 ms 193004 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -