Submission #732060

#	Time	Username	Problem	Language	Result	Execution time	Memory
732060		Trunkty	RMQ (NOI17_rmq)	C++14	100 / 100	215 ms	14568 KiB

rmq

#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,q;
vector<vector<int>> ranges[100005];

int segtree[400005],lazy[400005];

void pushdown(int node, int l, int r){
    segtree[node] += lazy[node];
    if(l!=r){
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node]; 
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int needl, int needr, int val){
    pushdown(node,l,r);
    if(l>needr or r<needl){
        return;
    }
    else if(l>=needl and r<=needr){
        lazy[node] += val;
        pushdown(node,l,r);
    }
    else{
        int mid = (l+r)/2;
        update(node*2,l,mid,needl,needr,val);
        update(node*2+1,mid+1,r,needl,needr,val);
        segtree[node] = min(segtree[node*2],segtree[node*2+1]);
    }
}

int pos; 

void walk(int node, int l, int r, int needl, int needr){
    pushdown(node,l,r);
    int mid = (l+r)/2;
    if(l>needr or r<needl){
        return;
    }
    else if(l>=needl and r<=needr){
        if(segtree[node]!=0){
            return;
        }
        if(l==r){
            pos = l;
        }
        else{
            pushdown(node*2,l,mid);
            pushdown(node*2+1,mid+1,r);
            if(segtree[node*2]==0){
                walk(node*2,l,mid,needl,needr);
            }
            else{
                walk(node*2+1,mid+1,r,needl,needr);
            }
        }
    }
    else{
        walk(node*2,l,mid,needl,needr);
        if(pos!=-1){
            return;
        }
        walk(node*2+1,mid+1,r,needl,needr);
    }
}

int ans[100005];

signed main(){
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
    cin >> n >> q;
    for(int i=1;i<=q;i++){
        int a,b,c;
        cin >> a >> b >> c;
        ranges[c].push_back({a,b});
        update(1,0,n-1,a,b,1);
    }
    for(int i=0;i<n;i++){
        int a=0,b=n-1;
        for(vector<int> j:ranges[i]){
            update(1,0,n-1,j[0],j[1],-1);
            a = max(a,j[0]);
            b = min(b,j[1]);
        }
        if(a>b){
            for(int j=1;j<=n;j++){
                cout << -1 << " ";
            }
            cout << "\n";
            return 0;
        }
        pos = -1;
        walk(1,0,n-1,a,b);
        if(pos==-1){
            for(int j=1;j<=n;j++){
                cout << -1 << " ";
            }
            cout << "\n";
            return 0;
        }
        ans[pos] = i;
        update(1,0,n-1,pos,pos,2e9);
    }
    for(int i=0;i<=n-1;i++){
        cout << ans[i] << " ";
    }
    cout << "\n";
	return 0;
}

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