Submission #1015396

# Submission time Handle Problem Language Result Execution time Memory
1015396 2024-07-06T10:08:19 Z keler RMQ (NOI17_rmq) C++14
0 / 100
0 ms 348 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define inf LLONG_MAX
#define pb push_back
#define lc 2*pos+1
#define rc 2*pos+2
#define halleluya  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

signed main(){
halleluya
    int n,q;cin>>n>>q;
    vector<pair<int,int>>rm[n];
    for (int i=1;i<=q;i++){
        int l,r,x;cin>>l>>r>>x;
        rm[l].pb({x,r});
    }
    set<int>ang;
    for (int i=0;i<n;i++) ang.insert(i);
    vector<pair<int,int>>num(n);
    priority_queue<pair<int,int>>pq;
    for (int i=0;i<n;i++){
        if (pq.size()){
            while (pq.top().second<i){
            pq.pop();
            if (pq.empty()) break;
        } 
        }
        if (rm[i].size()){
            for (auto x:rm[i]){
                pq.push({x.first,x.second});
            }
        }
        if (pq.size()){
            // cout<<pq.top().first<<" "<<i<<endl;
            num[i].first=pq.top().first;
            num[i].second=i;
        }
    }
    // for (auto x:num)cout<<x<<" ";
    // cout<<endl;
    sort(num.begin(),num.end(),greater<pair<int,int>>());
    int cur=-1;
    bool an=0;
    for (auto &[x,y]:num){
        // cout<<x<<" "<<y<<endl;
        if (cur!=x && cur!=-1){
            if (!an){
            while (n--) cout<<"-1"<<" ";
            return 0; 
        }
            an=0;
        }
        auto it=ang.lower_bound(x);
        if (it==ang.end()){
            while (n--){
                cout<<"-1"<<" ";
            }
            return 0; 
        }
        cur=x;
        if (*it==x) an=1;
        x=*it;
        // cout<<*it<<" "<<y<<endl;
        ang.erase(*it);
    }
    vector<int>ans(n);
    for (auto [x,y]:num) ans[y]=x;
    for (auto x:ans)cout<<x<<' ';
}

Compilation message

rmq.cpp: In function 'int main()':
rmq.cpp:47:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto &[x,y]:num){
      |                ^
rmq.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto [x,y]:num) ans[y]=x;
      |               ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -