oj.uz

답안 #659504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -