Submission #635640

#	Time	Username	Problem	Language	Result	Execution time	Memory
635640		PoonYaPat	RMQ (NOI17_rmq)	C++14	100 / 100	32 ms	3660 KiB

rmq

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,ans[100001];
pii pos[100001],wide[100001];
set<pii> s;
queue<int> q;
bool have[100001];

void exit() {
    for (int i=0; i<n; ++i) cout<<-1<<" ";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    memset(ans,-1,sizeof(ans));
    while (m--) {
        int l,r,val;
        cin>>l>>r>>val;
        if (!have[val]) {
            pos[val]={l,r};
            wide[val]={l,r};
            have[val]=true;
        } else {
            pos[val]={max(l,pos[val].first),min(r,pos[val].second)};
            wide[val]={min(l,wide[val].first),max(r,wide[val].second)};
        }
    }

    for (int i=n-1; i>=0; --i) {
        if (!have[i]) q.push(i);
        else {
            bool can=false;
            auto it=s.upper_bound(pii(wide[i].first,wide[i].second));
            int j=0;

            if (s.size()==0) {
                for (int j=wide[i].first; j<=wide[i].second; ++j) {
                    if (ans[j]==-1) {
                        if (!can && pos[i].first<=j && j<=pos[i].second) {
                            can=true;
                            ans[j]=i;
                        } else if (q.empty()) {
                            exit(); return 0;
                        } else {
                            ans[j]=q.front();
                            q.pop();
                        }
                    }
                }
                continue;
            }

            if (it==s.begin()) {
                for (j; j<(*it).second && j<=wide[i].second; ++j) {
                    if (ans[j]==-1) {
                        if (!can && pos[i].first<=j && j<=pos[i].second) {
                            can=true;
                            ans[j]=i;
                        } else if (q.empty()) {
                            exit(); return 0;
                        } else {
                            ans[j]=q.front();
                            q.pop();
                        }
                    }
                }
                ++it;
            }

            auto h=it; --h;
            while (j<=wide[i].second) {
                for (j=(*h).first+1; j<(*it).second && j<=wide[i].second; ++j) {
                    if (ans[j]==-1) {
                        if (!can && pos[i].first<=j && j<=pos[i].second) {
                            can=true;
                            ans[j]=i;
                        } else if (q.empty()) {
                            exit(); return 0;
                        } else {
                            ans[j]=q.front();
                            q.pop();
                        }
                    }
                }
                ++h; ++it;
            }


            if (!can) {
                exit();
                return 0;
            }

            s.insert(pii(wide[i].second,wide[i].first));
        }
    }

    for (int i=0; i<n; ++i) {
        if (ans[i]==-1) {
            if (q.empty()) {
                exit(); return 0;
            } else {
                ans[i]=q.front();
                q.pop();
            }
        }
    }

    for (int i=0; i<n; ++i) cout<<ans[i]<<" ";
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:57:22: warning: statement has no effect [-Wunused-value]
   57 |                 for (j; j<(*it).second && j<=wide[i].second; ++j) {
      |                      ^

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