Submission #298452

#	Time	Username	Problem	Language	Result	Execution time	Memory
298452		mat_v	Restore Array (RMI19_restore)	C++14	100 / 100	388 ms	1024 KiB

restore

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 100005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;
int x[maxn], y[maxn];
ll w[maxn];
int br = 1;
ll dist[5005];


int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    ff(i,0,n - 1){
        x[br] = i;
        y[br] = i+1;
        w[br] = 0;
        br++;
        x[br] = i+1;
        y[br] = i;
        w[br] = 1;
        br++;
    }
    ff(i,1,m){
        int a, b;
        int k;
        int val;
        cin >> a >> b >> k >> val;
        a++;
        b++;
        if(val == 0){
            /// barem (r - l + 1 - k + 1) keca
            x[br] = b;
            y[br] = a - 1;
            w[br] = b - a + 1 - k;
            br++;
        }
        else{
            /// maksimalno (r - l + 2 - k) keca
            x[br] = a - 1;
            y[br] = b;
            w[br] = k + a - 2 - b;
            br++;
        }
    }
    dist[0] = 0;
    ff(i,1,n)dist[i] = 1e9;

    ff(i,1,n){
        ff(j,1,br - 1){
            int p1 = x[j];
            int p2 = y[j];
            ll c = w[j];
            if(dist[p1] > dist[p2] + c)dist[p1] = dist[p2] + c;
        }
    }
    ff(j,1,br - 1){
        int p1 = x[j];
        int p2 = y[j];
        ll c = w[j];
        if(dist[p1] > dist[p2] + c){
            cout << -1 << "\n";
            return 0;
        }
    }
    ff(i,1,n){
        cout << dist[i] - dist[i - 1] << " ";
    }
    cout << "\n";
    return 0;

}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:35:5: note: in expansion of macro 'ff'
   35 |     ff(i,0,n - 1){
      |     ^~
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:45:5: note: in expansion of macro 'ff'
   45 |     ff(i,1,m){
      |     ^~
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:68:5: note: in expansion of macro 'ff'
   68 |     ff(i,1,n)dist[i] = 1e9;
      |     ^~
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:70:5: note: in expansion of macro 'ff'
   70 |     ff(i,1,n){
      |     ^~
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:71:9: note: in expansion of macro 'ff'
   71 |         ff(j,1,br - 1){
      |         ^~
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:78:5: note: in expansion of macro 'ff'
   78 |     ff(j,1,br - 1){
      |     ^~
restore.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
restore.cpp:87:5: note: in expansion of macro 'ff'
   87 |     ff(i,1,n){
      |     ^~

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