oj.uz

Submission #659504

# Submission time Handle Problem Language Result Execution time Memory
659504 2022-11-18T10:26:57 Z AlesL0 Restore Array (RMI19_restore) C++17
7 / 100
 221 ms 1204 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1000000000;

struct query {
    ll l, kk, bigger;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m; cin >> n >> m;
    vector <query> q[n+1];
    vector <ll> dpmin(n+1, -INF), dpmax(n+1, INF);
    dpmin[0] = 0;
    dpmax[0] = 0;
    while (m--){
        ll l, r, k, value; cin >> l >> r >> k >> value;
        r++; l++;
        if (value){
            q[r].push_back({l-1, r-l+2-k, 1});
        }
        else q[r].push_back({l-1, r-l+1-k, 0});
    }
    for (int i = 1; i <= n; i++){
        q[i].push_back({i-1, 0, 1});
        q[i].push_back({i-1, 1, 0});
    }
    for (int i = 1; i <= n; i++){
        for (auto x : q[i]){
            if (x.bigger)dpmin[i] = max(dpmin[i], dpmin[x.l]+x.kk);
            else dpmax[i] = min(dpmax[i], dpmax[x.l]+x.kk);
        }
        for (int j = i; j >= 1; j--){
            for (auto x : q[j]){
                if (x.bigger)dpmax[x.l] = min(dpmax[x.l], dpmax[j]-x.kk);
                else dpmin[x.l] = max(dpmin[x.l], dpmin[j]-x.kk);
            }
        }
    }
    //for (int i = 0; i <= n; i++)cerr << dpmin[i] << " " << dpmax[i] << "\n";
    for (int i = 0; i <= n; i++){
        if (dpmin[i] > dpmax[i]){
            cout << -1;
            return 0;
        }
    }
    for (int i = 0; i < n; i++)cout << dpmax[i+1]-dpmax[i] << " ";
}

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 1 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 320 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1176 KB Output is correct
2 Correct 216 ms 1108 KB Output is correct
3 Correct 216 ms 1188 KB Output is correct
4 Incorrect 215 ms 1204 KB Integer 2 violates the range [-1, 1]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1176 KB Output is correct
2 Correct 216 ms 1108 KB Output is correct
3 Correct 216 ms 1188 KB Output is correct
4 Incorrect 215 ms 1204 KB Integer 2 violates the range [-1, 1]
5 Halted 0 ms 0 KB -

Subtask #4
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 1 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 320 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 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 221 ms 1176 KB Output is correct
12 Correct 216 ms 1108 KB Output is correct
13 Correct 216 ms 1188 KB Output is correct
14 Incorrect 215 ms 1204 KB Integer 2 violates the range [-1, 1]
15 Halted 0 ms 0 KB -