oj.uz

Submission #730155

# Submission time Handle Problem Language Result Execution time Memory
730155 2023-04-25T11:02:31 Z welleyth Restore Array (RMI19_restore) C++17
0 / 100
 584 ms 134732 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int M = 10000;
constexpr int N = 5000;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

int n,m;
int l[M],r[M],k[M],value[M];
int a[N];
int sumL[N][N];
int sumR[N][N];
int pref[N];

bool ok(){
    for(int i = 0; i < n; i++){
        pref[i] = a[i];
        if(i) pref[i] += pref[i-1];
    }

    for(int i = 0; i < m; i++){
        int S = pref[r[i]];
        if(l[i]) S -= pref[l[i]-1];
        if(S > sumR[l[i]][r[i]])
            return false;
//        if(t && S < sumL[l[i]][r[i]])
//            return false;
    }
    return true;
}

bool ok1(){
    for(int i = 0; i < n; i++){
        pref[i] = a[i];
        if(i) pref[i] += pref[i-1];
    }

    for(int i = 0; i < m; i++){
        int S = pref[r[i]];
        if(l[i]) S -= pref[l[i]-1];
        if(S > sumR[l[i]][r[i]])
            return false;
        if(S < sumL[l[i]][r[i]])
            return false;
    }
    return true;
}

void solve(){
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        cin >> l[i] >> r[i] >> k[i] >> value[i];
    }

    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            sumL[i][j] = 0;
            sumR[i][j] = j - i + 1;
        }
    }

    set<pair<int,int>> segs;

    for(int i = 0; i < m; i++){
        if(value[i] == 0)
            sumR[l[i]][r[i]] = min(sumR[l[i]][r[i]],r[i]-l[i]+1-k[i]);
        else
            sumL[l[i]][r[i]] = max(sumL[l[i]][r[i]],r[i]-l[i]+1-k[i]+1);
        segs.insert(make_pair(l[i],r[i]));
    }

    for(int i = 0; i < m; i++){
        if(sumL[l[i]][r[i]] > sumR[l[i]][r[i]]){
            cout << "-1\n";
            return;
        }
    }

    int c[n+1];
    memset(c,0,sizeof c);
    for(auto&[tl,tr] : segs){
        c[tl]++;
        c[tr+1]--;
    }

    for(int i = 1; i < n; i++){
        c[i] += c[i-1];
    }
    vector<pair<int,int>> order;
    for(int i = 0; i < n; i++){
        order.push_back(make_pair(c[i],i));
    }
    sort(order.rbegin(),order.rend());

    for(auto&[cc,i] : order){
        a[i] = 1;
        if(ok()) continue;
        a[i] = 0;
    }

//    for(int i = 0; i < m; i++){
//        cout << sumL[l[i]][r[i]] << " " << sumR[l[i]][r[i]] << "\n";
//    }

//    for(int i = 0; i < n; i++) cout << a[i] << " ";
//    cout << "\n";

    if(!ok1()){
        cout << "-1\n";
        return;
    }

    for(int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n";

    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }
    return 0;
}
/**

k-th [l..r] = value

value == 0 -> cnt0 >= k
value == 1 -> cnt0 < k

cnt0 = (r - l + 1) - sum[l..r] = (r - l + 1) - cnt1

value == 0
cnt0 >= k
(r - l + 1) - cnt1 >= k
(r - l + 1) - k >= cnt1
cnt1 <= (r - l + 1) - k

value == 1
cnt0 < k
(r - l + 1) - cnt1 < k
(r - l + 1) - k < cnt1
cnt1 > (r - l + 1) - k

**/

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 134656 KB Output is correct
2 Correct 563 ms 133012 KB Output is correct
3 Correct 577 ms 134732 KB Output is correct
4 Incorrect 584 ms 132660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 134656 KB Output is correct
2 Correct 563 ms 133012 KB Output is correct
3 Correct 577 ms 134732 KB Output is correct
4 Incorrect 584 ms 132660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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