Submission #568164

#	Time	Username	Problem	Language	Result	Execution time	Memory
568164		birthdaycake	Restore Array (RMI19_restore)	C++17	0 / 100	68 ms	5524 KiB

restore

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 

vector<pair<int,int>>adj[200001];
int dist[200001];
signed main(){
    
    boost;
    
    int n,m; cin >> n >> m;
    vector<pair<int,pair<int,int>>>d;
    for(int i = 0; i < m; i++){
        int l,r,k,v; cin >> l >> r >> k >> v;
        l++; r++;
        int a = r - l + 2 - k, b = r - l + 1 - k;
        if(v == 1){
            d.push_back({r,{l - 1, -a}});
        }else{
            d.push_back({l - 1, {r,b}});
        }
    }
    for(int i = 0; i < n; i++){
        adj[i].push_back({i + 1, 1});
        adj[i + 1].push_back({i, 0});
    }
    for(int i = 1; i <= n; i++) dist[i] = 1e18;
    
    dist[0] = 0;
    for(int i = 0; i < n + 1; i++){
        for(auto s:d){
            if(dist[s.first] != 1e18 && dist[s.first] + s.second.second < dist[s.second.first]){
                dist[s.second.first] = dist[s.first] + s.second.second;
                if(i == n - 1){
                    cout << "-1";
                    return 0;
                }
            }
        }
    }
    int x = 0;
    for(int i = 1; i <= n; i++){
        if(dist[i] > x){
            x++;
            cout << "1";
        }else{
            cout << "0";
        }
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55