oj.uz

Submission #272056

# Submission time Handle Problem Language Result Execution time Memory
272056 2020-08-18T08:30:07 Z egekabas Restore Array (RMI19_restore) C++14
13 / 100
 487 ms 888 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct seg{
    int l, r, type, cnt; 
};
int n, m;
seg a[10009];
int ans[10009];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        cin >> a[i].l >> a[i].r >> a[i].cnt >> a[i].type;
        if(a[i].type == 1)
            a[i].cnt = a[i].r-a[i].l+2-a[i].cnt;
    }
    for(int i = 0; i < n; ++i){
        pii mini = {1e9, 1e9};
        for(int j = 0; j < m; ++j){
            if(a[j].cnt <= 0 || a[j].l > i || a[j].r < i)
                continue;
            mini = min(mini, {a[j].r, j});
        }
        if(mini.ff == 1e9)
            continue;
        ans[i] = a[mini.ss].type;
        for(int j = 0; j < m; ++j)
            if(a[j].l <= i && i <= a[j].r && ans[i] == a[j].type)
                a[j].cnt--;
    }
    for(int j = 0; j < m; ++j)
        if(a[j].cnt > 0){
            cout << "-1\n";
            return 0;
        }
    for(int i = 0; i < n; ++i)
        cout << ans[i] << ' ';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 664 KB Output is correct
2 Correct 271 ms 764 KB Output is correct
3 Correct 250 ms 796 KB Output is correct
4 Correct 266 ms 632 KB Output is correct
5 Correct 455 ms 668 KB Output is correct
6 Correct 425 ms 632 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 664 KB Output is correct
2 Correct 271 ms 764 KB Output is correct
3 Correct 250 ms 796 KB Output is correct
4 Correct 266 ms 632 KB Output is correct
5 Correct 455 ms 668 KB Output is correct
6 Correct 425 ms 632 KB Output is correct
7 Correct 358 ms 760 KB Output is correct
8 Correct 355 ms 700 KB Output is correct
9 Correct 361 ms 760 KB Output is correct
10 Correct 337 ms 768 KB Output is correct
11 Correct 478 ms 888 KB Output is correct
12 Correct 487 ms 820 KB Output is correct
13 Correct 326 ms 688 KB Output is correct
14 Correct 427 ms 760 KB Output is correct
15 Correct 371 ms 768 KB Output is correct
16 Incorrect 382 ms 760 KB Output isn't correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -