結果

問題 No.1675 Strange Minimum Query
ユーザー houren
提出日時 2021-09-10 22:07:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,147 bytes
コンパイル時間 1,835 ms
コンパイル使用メモリ 185,072 KB
実行使用メモリ 17,696 KB
最終ジャッジ日時 2024-06-12 00:22:24
合計ジャッジ時間 6,209 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000000;
using P = pair<int,int>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()

int main(){
    int n,q;
    bool B = false;
    cin >> n >> q;
    vector<vector<P>> x(n+1);
    vector<int> ans(n);
    rep(i,q){
        int l,r,b;
        cin >> l >> r >> b;
        l--;
        x[l].push_back(make_pair(b,1));
        x[r].push_back(make_pair(b,0));
    }
    map<int,pair<int,bool>> mp;
    rep(i,n){
        for(auto now : x[i]){
            int y,z;
            tie(y,z) = now;
            if(z){
                mp[y].first++;
                mp[y].second = false;
            }
            else{
                if(!mp[y].second) B = true;
                mp[y].first--;
            }
            if(!mp[y].first) mp.erase(y);
        }
        if(mp.size()){
            auto it = max_element(all(mp));
            ans[i] = (*it).first;
            (*it).second.second = true;
        }
        else ans[i] = MOD;
    }
    if(B) cout << -1;
    else rep(i,n) cout << ans[i] << " ";
    cout << endl;
    return 0;
}
0