049 - Flip Digits 2（★6）- xor基底を利用した非想定解。1が連続した1区間であることを利用すると掃き出しの計算量が激減する (naoya_t)

049.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
 
ll solve(int N, int M, vi& c, vi& l, vi& r) {
    using P = tuple<int, int, int>;
    PQ(P) pq;
    rep(i,M) pq.emplace(l[i], c[i], r[i]);
 
    ll cost = 0;
    rep(i,N){
        if (pq.empty() || get<0>(pq.top()) > i) return -1;
        auto [li, ci, ri] = pq.top(); pq.pop();
        cost += ci;
        while (!pq.empty() && get<0>(pq.top()) == i) {
            auto [lj, cj, rj] = pq.top(); pq.pop();
            if (rj == ri) continue;
            pq.emplace(min(ri,rj), cj, max(ri,rj));
        }
    }
    return cost;
}
 
int main() {
    int N, M; scanf("%d %d%*c", &N, &M);
    vi c(M), l(M), r(M);
    rep(i,M){
        scanf("%d %d %d%*c", &c[i], &l[i], &r[i]);
        --l[i];
    }
    printf("%lld\n", solve(N,M,c,l,r));
    return 0;
}

challenge.md

ジャッジは通るが、最悪計算量はO(n^2)で

100000 100000
1 1 1
1 1 2
1 1 3
...
1 1 99999
1 1 100000

のような入力で落とせる。