oj.uz

Submission #591192

# Submission time Handle Problem Language Result Execution time Memory
591192 2022-07-07T01:53:00 Z codebuster_10 Restore Array (RMI19_restore) C++17
100 / 100
 362 ms 840 KB 
#include <bits/stdc++.h>
//#define int int64_t //be careful about this 

using namespace std;

#define vt vector 
#define ar array 
#define pr pair 

#define f first 
#define s second

#define pb push_back
#define eb emplace_back

#define fr(i,a,b) for(int i = (a); i < (b); ++i)
#define rf(i,a,b) for(int i = (b)-1; i >= (a); --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace IN{
  template<class T> void re(vector<T> &A);
  template<class S,class T> void re(pair<S,T> &A);
  template<class T,size_t N> void re(array<T,N> &A);

  template<class T> void re(T& x){ 
    cin >> x;}
  template<class H, class... T> void re(H& h, T&... t){ 
    re(h); re(t...);}

  template<class T> void re(vector<T> &A){ 
    for(auto& x : A) re(x);}
  template<class S,class T> void re(pair<S,T> &A){ 
      re(A.first); re(A.second);}
  template<class T,size_t N> void re(array<T,N> &A){
    for(int i = 0; i < N; ++i)  re(A[i]);}
}

namespace OUT{
  template<class T>
  void __p(const T& a){ cout<<a; }
  template<class T, class F>
  void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
  template<class T, size_t N>
  void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
  template<class T>
  void __p(const vector<T>& a){
    cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
  template<class T, class ...Arg>
  void __p(T a1, Arg ...a){__p(a1); __p(a...); }
  template<class Arg1>
  void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
  template<class Arg1, class ... Args>
  void __f(const char *ss, Arg1 &&arg1, Args &&... args){
    int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
    const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}


namespace FUNC{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }

  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
#endif
  }

  template<class T> bool ckmin(T& a, const T& b){ 
    return b < a ? a = b, true : false; }
    
  template<class T> bool ckmax(T& a, const T& b){ 
    return a < b ? a = b, true : false; }

  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  int my_rand(int L, int R){ 
    return uniform_int_distribution<int>(L,R)(rng); }
  
  template<class T> int sz(const T& x){ 
    return int(x.size()); }

  template<class T> int lb(const vector<T>& vec,const T& val){
    return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  template<class T> int ub(const vector<T>& vec,const T& val){
    return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  constexpr int  dx[4] = {1,0,-1,0};
  constexpr int  dy[4] = {0,1,0,-1};
  constexpr char dr[4] = {'D','R','U','L'};

  constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
  constexpr int INF = 2e9;

  template<class T>
  vector<T> V(int n,T val){
    return vector<T> (n,val);
  }

  template<class T>
  vector<vector<T>> V(int n,int m,T val){
    return vector<vector<T>> (n,vector<T> (m,val));
  }

  template<class T>
  vector<vector<vector<T>>> V(int n,int m,int k,T val){
    return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
  }
}


using namespace IN;
using namespace OUT;
using namespace FUNC;
























signed main(){
  IO();

  int n,m;
  re(n,m);

  vt<ar<int,3>> edges;

  auto add_constraint = [&](int j,int i,int w){
    edges.pb({i,j,w});
  };

  fr(i,1,n+1){
    add_constraint(i,i-1,1);
    add_constraint(i-1,i,0);
  }

  while(m--){
    int l,r,k,val;
    re(l,r,k,val);
    ++l,++r;
    if(val == 0){
      add_constraint(r,l-1,r-l+1-k);
    }else{
      add_constraint(l-1,r,k-1-r+l-1);
    }
  }

  const int S = n + 1;

  fr(i,0,n+1) edges.pb({S,i,0});

  vt<int> d(S + 1,INF);

  d[S] = 0;

  fr(_,0,S){
    for(auto [u,v,w] : edges)
      ckmin(d[v],d[u]+w);
  }

  for(auto [u,v,w] : edges)
    if(ckmin(d[v],d[u]+w)){
      cout << "-1";
      return 0;
    }

  fr(i,1,n+1){
    cout << d[i] - d[i-1] << " ";
  }

  // output_run_time();
  return 0;
}

Compilation message

restore.cpp: In function 'void FUNC::IO(std::string)':
restore.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |       freopen((s+".in").c_str(),"r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
restore.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       freopen((s+".out").c_str(),"w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 788 KB Output is correct
2 Correct 142 ms 788 KB Output is correct
3 Correct 129 ms 788 KB Output is correct
4 Correct 127 ms 788 KB Output is correct
5 Correct 329 ms 832 KB Output is correct
6 Correct 323 ms 788 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 788 KB Output is correct
2 Correct 142 ms 788 KB Output is correct
3 Correct 129 ms 788 KB Output is correct
4 Correct 127 ms 788 KB Output is correct
5 Correct 329 ms 832 KB Output is correct
6 Correct 323 ms 788 KB Output is correct
7 Correct 149 ms 788 KB Output is correct
8 Correct 135 ms 788 KB Output is correct
9 Correct 131 ms 788 KB Output is correct
10 Correct 133 ms 788 KB Output is correct
11 Correct 362 ms 788 KB Output is correct
12 Correct 351 ms 788 KB Output is correct
13 Correct 164 ms 840 KB Output is correct
14 Correct 128 ms 788 KB Output is correct
15 Correct 140 ms 788 KB Output is correct
16 Correct 163 ms 788 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 145 ms 788 KB Output is correct
12 Correct 142 ms 788 KB Output is correct
13 Correct 129 ms 788 KB Output is correct
14 Correct 127 ms 788 KB Output is correct
15 Correct 329 ms 832 KB Output is correct
16 Correct 323 ms 788 KB Output is correct
17 Correct 149 ms 788 KB Output is correct
18 Correct 135 ms 788 KB Output is correct
19 Correct 131 ms 788 KB Output is correct
20 Correct 133 ms 788 KB Output is correct
21 Correct 362 ms 788 KB Output is correct
22 Correct 351 ms 788 KB Output is correct
23 Correct 164 ms 840 KB Output is correct
24 Correct 128 ms 788 KB Output is correct
25 Correct 140 ms 788 KB Output is correct
26 Correct 163 ms 788 KB Output is correct
27 Correct 132 ms 788 KB Output is correct
28 Correct 126 ms 788 KB Output is correct
29 Correct 135 ms 768 KB Output is correct
30 Correct 156 ms 836 KB Output is correct
31 Correct 144 ms 788 KB Output is correct
32 Correct 123 ms 788 KB Output is correct
33 Correct 337 ms 788 KB Output is correct
34 Correct 346 ms 788 KB Output is correct
35 Correct 145 ms 788 KB Output is correct
36 Correct 137 ms 788 KB Output is correct