Submission #775501

#	Time	Username	Problem	Language	Result	Execution time	Memory
775501		Cookie	RMQ (NOI17_rmq)	C++14	100 / 100	79 ms	19760 KiB

rmq

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("HAMMING.INP");
ofstream fout("HAMMING.OUT");
#define sz(a) (int)a.size()
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
 const ll mod = 1e9 + 7,inf = 2e9;
const int mxn = 2e5 + 5, sq = 400, mxv = 1e6 + 5;
int n, q;
pii st[4 * mxn + 1];
int lid[mxn + 1], rid[mxn + 1];
void upd(int nd, int l, int r, int id, int v){
    if(id < l || id > r)return;
    if(l == r){
        st[nd] = make_pair(v, id); return;
    }
    int mid = (l + r) >> 1;
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    st[nd] = min(st[nd << 1], st[nd << 1 | 1]);
}
pii get(int nd, int l, int r, int ql, int qr){
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    if(qr <= mid){
        return(get(nd << 1, l, mid, ql, qr));
    }else if(ql > mid){
        return(get(nd << 1 | 1, mid + 1, r, ql, qr));
    }else{
        return(min(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
    }
}
vt<pii>events[mxn + 1];
int ans[mxn + 1];
void no(){
    for(int i = 0; i < n; i++)cout << -1 << " ";
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        lid[i] = 0; rid[i] = n - 1;
    }
    for(int i = 0; i < q; i++){
        int l, r, v; cin >> l >> r >> v;
        lid[v] = max(lid[v], l); rid[v] = min(rid[v], r);
        events[l].pb({1, v}); events[r + 1].pb({-1, v});
    }
    
    multiset<int>ms;
    ms.insert(0);
    for(int i = 0; i < n; i++){
        for(auto [type, v]: events[i]){
            if(type == 1){
                ms.insert(v);
            }else{
                ms.erase(ms.find(v));
            }
        }
        upd(1, 0, n - 1, i, *ms.rbegin());
    }
    
    for(int i = 0; i < n; i++){
        if(lid[i] > rid[i]){
            no();
            return(0);
        }else{
            pii val = get(1, 0, n - 1, lid[i], rid[i]);
            if(val.first > i){
                no();
                return(0);
            }else{
                ans[val.second] = i;
                upd(1, 0, n - 1, val.second, inf);
            }
        }
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
    }
    
    return(0);
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:69:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for(auto [type, v]: events[i]){
      |                  ^

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33