oj.uz

답안 #519232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519232 2022-01-26T04:54:26 Z hohohaha Restore Array (RMI19_restore) C++14
0 / 100
 9 ms 7996 KB 
#include<bits/stdc++.h> 
using namespace std;
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--)
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define ii pair<int, int>
#define pb push_back
#define pf push_front
#define em emplace
#define ef emplace_front
#define eb emplace_back
#define om pop
#define of pop_front
#define ob pop_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 
#define rand rng
#define endl '\n'
#define sp ' '
void solve(); 
signed main() { 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
	int test_num = 1; 
	fori(test, 1, test_num) { 
		solve(); 
	}
}
#define int long long
const int maxn = 1e5 + 5, inf = LLONG_MAX / 100ll; 
int n, m; 
vector<pair<int, int> > g[maxn]; 	
int pref[maxn]; 
bool inq[maxn]; 
int up_cnt[maxn];  
void solve() { 
	cin >> n >> m; 
	fori(i, 1, n) { 
		g[i].eb(i - 1, 0); 
	 	g[i - 1].eb(i, 1); 
	 }
	fori(i, 1, m) { 
		int l, r, k, val; 
		cin >> l >> r >> k >> val; l++; r++; 
		if(val == 0) {
			g[l - 1].eb(r, (r - l + 1) - k); 
		}
		else { 
			g[r].eb(l - 1, -((r - l + 1) - k + 1)); 
		}
	}
	fill(all(pref), inf); 
	pref[0] = 0; 
	queue<int> q; q.em(0); inq[0] = 1; 
	while(q.size()) { 
		int u = q.front(); q.pop(); inq[u] = 0; 
		assert(1 <= u and u <= n); 
		for(ii e: g[u]) { 
			int v = e.fi, w = e.se; 
			assert(1 <= v and v <= n); 
			if(pref[v] > pref[u] + w) { 
				pref[v] = pref[u] + w; 
				up_cnt[v]++; 
				if(up_cnt[v] > n or pref[v] < 0) { 
					cout << -1; 
					return; 
				}
				if(!inq[v]) { 
					q.em(v); 
					inq[v] = 1; 
				}
			}
		}
	}
	fori(i, 1, n) { 
		cout << pref[i] - pref[i - 1] << sp; 
	}
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 6752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 7996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 7996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 6752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -