Submission #1200017

#TimeUsernameProblemLanguageResultExecution timeMemory
1200017abdelaal_03Restore Array (RMI19_restore)C++20
0 / 100
82 ms836 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") typedef long long ll; typedef long double ld; typedef long long ll; const long double PI = 3.141592654; const long long md = 1e9 + 7; #define xi first #define yi second #define MAX int(3e5)+7 #define INF (ll)1e9 #define SQ 500 long long gcd(long long a, long long b) { if (b == 0)return a; return (a % b) ? gcd(b, a % b) : b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin>>n>>m; vector<pair<int, pair<int, int>>>edg(m); for (int i = 0; i < m; i++) { int l, r, k, val; cin>>l>>r>>k>>val; l++, r++; if (val == 0) { edg[i] = {r - l + 1 - k,{l - 1, r}}; }else { edg[i] = {(r - l + 1 - k + 1) * -1,{r, l - 1}}; } } for (int i = 1; i <= n; i++) { edg.push_back({1,{i - 1, i}}); } for (int i = 0; i <= n; i++) { edg.push_back({0,{n + 1, i}}); } vector<ll> d(n + 2, INF); d[n + 1] = d[0] = 0; int x; for (int i = 0; i < n + 2; i++) { x = -1; for (auto &e : edg) { if (d[e.yi.xi] < INF) { if (d[e.yi.yi] > d[e.yi.xi] + e.xi) { d[e.yi.yi] = max(-INF, d[e.yi.xi] + e.xi); x = e.yi.yi; } } } } if (x == -1) { for (int i = 1; i <= n; i++) cout<<d[i] - d[i - 1]<<" "; }else cout<<-1<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...