結果

問題 No.1675 Strange Minimum Query
ユーザー hir355
提出日時 2021-09-10 21:41:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 543 ms / 2,000 ms
コード長 7,965 bytes
コンパイル時間 2,591 ms
コンパイル使用メモリ 215,944 KB
最終ジャッジ日時 2025-01-24 10:00:42
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
// using namespace atcoder;

constexpr long long INF_LL = 2000000000000000000LL;
constexpr int INF = 100000000;
constexpr long long MOD = 998244353;

#define all(x) x.begin(), x.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) REP(i, 0, n)

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<ll> vl;

int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int sign[2] = {1, -1};

template <class T> bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}

ll modpow(ll a, ll b, ll m) {
    if(b == 0)
        return 1;
    ll t = modpow(a, b / 2, m);
    if(b & 1) {
        return (t * t % m) * a % m;
    } else {
        return t * t % m;
    }
}

struct edge {
    int to;
    ll cost;
    edge(int t, ll c) { to = t, cost = c; }
};

typedef vector<vector<int>> graph;

// using mint = modint998244353;
// constexpr int MAX_COM = 100001;
// mint fac[MAX_COM], ifac[MAX_COM];
// void initfac() {
//     fac[0] = ifac[0] = 1;
//     REP(i, 1, MAX_COM) fac[i] = i * fac[i - 1];
//     REP(i, 1, MAX_COM) ifac[i] = 1 / fac[i];
// }
// mint nCr(int n, int r){
//     if(r < 0 || n < r) return 0;
//     return fac[n] * ifac[n - r] * ifac[r];
// }

// typedef int S;
// S op(S x, S y){ return max(x, y); }
// S e(){ return 0; }
// typedef int F;
// S mapping(F f, S x){ return f + x; }
// F composition(F f, F g){ return f + g; }
// F id(){ return 0; }

class SegTreeBeats{
    unsigned int n;
    std::vector<long long> width,min[2],minc,max[2],maxc,sum,lazy;
    void eval(int k){
        if(n-1<=k)return;
        if(lazy[k]){
            update_node_add(2*k+1,lazy[k]);
            update_node_add(2*k+2,lazy[k]);
            lazy[k]=0;
        }
        if(max[0][k]<max[0][2*k+1]){
            update_node_max(2*k+1,max[0][k]);
        }
        if(min[0][k]>min[0][2*k+1]){
            update_node_min(2*k+1,min[0][k]);
        }
        if(max[0][k]<max[0][2*k+2]){
            update_node_max(2*k+2,max[0][k]);
        }
        if(min[0][k]>min[0][2*k+2]){
            update_node_min(2*k+2,min[0][k]);
        }
    }
    void combine(int k){
        sum[k]=sum[2*k+1]+sum[2*k+2];
        if(min[0][2*k+1]<min[0][2*k+2]){
            min[0][k]=min[0][2*k+1];
            minc[k]=minc[2*k+1];
            min[1][k]=std::min(min[1][2*k+1],min[0][2*k+2]);
        }
        else if(min[0][2*k+1]>min[0][2*k+2]){
            min[0][k]=min[0][2*k+2];
            minc[k]=minc[2*k+2];
            min[1][k]=std::min(min[0][2*k+1],min[1][2*k+2]);
        }
        else{
            min[0][k]=min[0][2*k+1];
            minc[k]=minc[2*k+1]+minc[2*k+2];
            min[1][k]=std::min(min[1][2*k+1],min[1][2*k+2]);
        }
        if(max[0][2*k+1]>max[0][2*k+2]){
            max[0][k]=max[0][2*k+1];
            maxc[k]=maxc[2*k+1];
            max[1][k]=std::max(max[1][2*k+1],max[0][2*k+2]);
        }
        else if(max[0][2*k+1]<max[0][2*k+2]){
            max[0][k]=max[0][2*k+2];
            maxc[k]=maxc[2*k+2];
            max[1][k]=std::max(max[0][2*k+1],max[1][2*k+2]);
        }
        else{
            max[0][k]=max[0][2*k+1];
            maxc[k]=maxc[2*k+1]+maxc[2*k+2];
            max[1][k]=std::max(max[1][2*k+1],max[1][2*k+2]);
        }
    }
    void update_node_max(int k,long long x){
        sum[k]+=(x-max[0][k])*maxc[k];
        if(max[0][k]==min[0][k])min[0][k]=x;
        else if(max[0][k]==min[1][k])min[1][k]=x;
        max[0][k]=x;
    }
    void update_node_min(int k,long long x){
        sum[k]+=(x-min[0][k])*minc[k];
        if(min[0][k]==max[0][k])max[0][k]=x;
        else if(min[0][k]==max[1][k])max[1][k]=x;
        min[0][k]=x;
    }
    void update_node_add(int k,long long x){
        min[0][k]+=x;
        if(min[1][k]!=INF_LL)min[1][k]+=x;
        max[0][k]+=x;
        if(max[1][k]!=-INF_LL)max[1][k]+=x;
        sum[k]+=x*width[k];
        lazy[k]+=x;
    }
public:
    SegTreeBeats(unsigned int size,long long def=0){
        *this=SegTreeBeats(std::vector<long long>(size,def));
    }
    SegTreeBeats(std::vector<long long> initvec){
        n=1;
        while(n<initvec.size())n*=2;
        width.resize(2*n-1);
        min[0].resize(2*n-1);min[1].resize(2*n-1,INF_LL);
        minc.resize(2*n-1);
        max[0].resize(2*n-1);max[1].resize(2*n-1,-INF_LL);
        maxc.resize(2*n-1);
        sum.resize(2*n-1);
        lazy.resize(2*n-1);
        for(int i=n-1;i<n-1+initvec.size();i++){
            min[0][i]=max[0][i]=sum[i]=initvec[i-n+1];
            minc[i]=maxc[i]=1;
        }
        for(int i=n-2;i>=0;i--){
            combine(i);
        }
        width[0]=n;
        for(int i = 0; i < 2*n-2; i++) width[i]=width[(i-1)/2]/2;
    }
    void update_chmin(int a,int b,long long x,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(b<=l||r<=a||max[0][k]<=x)return;
        if(a<=l&&r<=b&&max[1][k]<x){
            update_node_max(k,x);
            return;
        }
        eval(k);
        update_chmin(a,b,x,2*k+1,l,(l+r)/2);
        update_chmin(a,b,x,2*k+2,(l+r)/2,r);
        combine(k);
    }
    void update_chmax(int a,int b,long long x,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(b<=l||r<=a||x<=min[0][k])return;
        if(a<=l&&r<=b&&x<min[1][k]){
            update_node_min(k,x);
            return;
        }
        eval(k);
        update_chmax(a,b,x,2*k+1,l,(l+r)/2);
        update_chmax(a,b,x,2*k+2,(l+r)/2,r);
        combine(k);
    }
    void update_add(int a,int b,long long x,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(b<=l||r<=a)return;
        if(a<=l&&r<=b){
            update_node_add(k,x);
            return;
        }
        eval(k);
        update_add(a,b,x,2*k+1,l,(l+r)/2);
        update_add(a,b,x,2*k+2,(l+r)/2,r);
        combine(k);
    }
    void update(int a,int b,long long x){
        update_chmin(a,b,x);
        update_chmax(a,b,x);
    }
    long long query_sum(int a,int b,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(b<=l||r<=a)return 0;
        if(a<=l&&r<=b)return sum[k];
        eval(k);
        long long vl=query_sum(a,b,2*k+1,l,(l+r)/2);
        long long vr=query_sum(a,b,2*k+2,(l+r)/2,r);
        return vl+vr;
    }
    long long query_min(int a,int b,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(b<=l||r<=a)return INF_LL;
        if(a<=l&&r<=b)return min[0][k];
        eval(k);
        long long vl=query_min(a,b,2*k+1,l,(l+r)/2);
        long long vr=query_min(a,b,2*k+2,(l+r)/2,r);
        return std::min(vl,vr);
    }
    long long query_max(int a,int b,int k=0,int l=0,int r=-1){
        if(r==-1)r=n;
        if(b<=l||r<=a)return -INF_LL;
        if(a<=l&&r<=b)return max[0][k];
        eval(k);
        long long vl=query_max(a,b,2*k+1,l,(l+r)/2);
        long long vr=query_max(a,b,2*k+2,(l+r)/2,r);
        return std::max(vl,vr);
    }
};

void solve(){
    int n, q;
    cin >> n >> q;
    vector<pair<pair<int, int>, int>> a(q);
    rep(i, q){
        cin >> a[i].first.first >> a[i].first.second >> a[i].second;
    }
    sort(all(a), [](auto &x, auto &y){return x.second < y.second;});
    SegTreeBeats seg(n, 1);
    for(auto [p, x] : a){
        auto [l, r] = p;
        seg.update_chmax(l - 1, r, x);
    }
    for(auto [p, x] : a){
        auto [l, r] = p;
        if(seg.query_min(l - 1, r) != x){
            cout << -1 << endl;
            return;
        }
    }
    rep(i, n - 1){
        cout << seg.query_sum(i, i + 1) << " ";
    }
    cout << seg.query_sum(n - 1, n) << endl;
}

int main(){
    cin.tie(0);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(16);

    // initfac();
    int t;
    t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}
0