Submission #1300610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300610		NotLinux	Restore Array (RMI19_restore)	C++20	100 / 100	405 ms	1156 KiB

restore

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int inf = 1e9 + 7;
void solve(){
    int n,m;
    cin >> n >> m;
   	vector<pair<int,int>>graph[n+1];
   	for(int i = 0;i<n;i++){
   		graph[i].push_back({i+1 , 1});
   		graph[i+1].push_back({i , 0});
   	}
   	while(m--){
   		int l,r,k,value;
   		cin >> l >> r >> k >> value;
   		l++ , r++;
   		int len = r-l+1;
   		if(value){// 1 ler
   			// cout << "flag0" << endl;
   			graph[r].push_back({l-1 , -(len-k+1)});
   			// cout << r << " -> " << l-1 << " | " << -k << endl;
   		}
   		else{// 0 lar
   			// cout << "flag1" << endl;
   			graph[l-1].push_back({r , len-k});
   			// cout << l-1 << " -> " << r << " | " << len-k << endl;
   		}
   	}
   	// belmman ford
   	vector<int>dist(n+1,inf);
   	dist[0] = 0;
   	for(int i = 0;i<=n+1;i++){
   		bool work = 0;
   		for(int node = 0;node<=n;node++){
   			for(auto itr : graph[node]){
   				if(dist[itr.first] > dist[node] + itr.second){
   					dist[itr.first] = dist[node] + itr.second;
   					work = 1;
   				}
   			}
   		}
   		if(work == 0)break;
   		if(i == n+1 and work){
   			cout << -1 << endl;
   			return;
   		}
   	}
   	// cout << "dist : ";for(int i = 0;i<=n;i++)cout << dist[i] << " ";cout << endl;
   	for(int i = 1;i<=n;i++){
   		if(dist[i] == dist[i-1])cout << "0 ";
   		else cout << "1 ";
   	}
   	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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