oj.uz

Submission #659498

# Submission time Handle Problem Language Result Execution time Memory
659498 2022-11-18T10:21:28 Z AlesL0 Restore Array (RMI19_restore) C++17
13 / 100
 233 ms 1228 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 << dpmin[i+1]-dpmin[i] << " ";
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 1172 KB Output is correct
2 Correct 213 ms 1228 KB Output is correct
3 Correct 223 ms 1196 KB Output is correct
4 Correct 217 ms 1200 KB Output is correct
5 Correct 226 ms 1200 KB Output is correct
6 Correct 210 ms 1184 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 1172 KB Output is correct
2 Correct 213 ms 1228 KB Output is correct
3 Correct 223 ms 1196 KB Output is correct
4 Correct 217 ms 1200 KB Output is correct
5 Correct 226 ms 1200 KB Output is correct
6 Correct 210 ms 1184 KB Output is correct
7 Correct 233 ms 1212 KB Output is correct
8 Correct 227 ms 1224 KB Output is correct
9 Incorrect 231 ms 1216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -