2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

チーム練でやった https://codeforces.com/gym/102433

BCLMは気づいたら通ってた

E

個数+1 を種類ごとに掛け合わせる

D

減らすのは/2で増やすのは+1しかないので適当にシミュレーション

I

同時に入れられないやつに辺をはると最大独立集合
swapのparityを考えると二部グラフなので求まる

A

全方位木DP
パスの重みパスの重み を求めたい
1項目は 部分木内の頂点重み辺重み
2項目は 部分木の頂点数辺重み

1項目は dp[v] = sum(dp[c] + (辺v-cの重み)*(部分木cの頂点重み))
2項目は num[v] = sum(num[c] + (辺v-cの重み)*(部分木cの頂点数))

あとはこれを全方位にする

K

セグ木もって頑張る
キャッシュの方は最後にロードされた の列を覚えておく
メモリの方は 個の区間加算ができるセグ木をもっておく

クエリ2がきたタイミングでキャッシュの 番目の情報をセグ木から取る
ただし、キャッシュに書き込んだあとにメモリを+1していると書き込んだ後の更新分まで反映してしまってまずい

クエリ2で答える場所について、何番目のクエリまでの情報で答えればよいか？をクエリ先読みで求めておく
クエリ1が来るたびその範囲にクエリ番号を更新しておいて、クエリ2がきたときにその位置を記憶しておくとできる
この情報を元にクエリ2の答えを求める

添字間違えて実装間に合わなくて涙

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll,ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
#ifdef DEBUG  
#include "../../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
  
template <typename Monoid>  
struct lazysegtree {  
    using T = typename Monoid::T;  
    using E = typename Monoid::E;  
    int n, height;  
    vector<T> dat;  
    vector<E> lazy;  
  
    lazysegtree() {}  
    lazysegtree(int n_) {  
        n = 1, height = 0;  
        while(n <= n_) { n *= 2; height++; }  
        dat.assign(n*2, Monoid::dt());  
        lazy.assign(n*2, Monoid::de());  
    }  
    void init(int n_) {  
        n = 1, height = 0;  
        while(n <= n_) { n *= 2; height++; }  
        dat.assign(n*2, Monoid::dt());  
        lazy.assign(n*2, Monoid::de());  
    }  
    void build(vector<T> v) {  
        REP(i, v.size()) dat[i+n] = v[i];  
        for(int i=n-1; i>0; --i) dat[i] = Monoid::f(dat[i*2], dat[i*2+1]);  
    }  
  
    inline T reflect(int k) { return lazy[k]==Monoid::de()?dat[k]:Monoid::g(dat[k], lazy[k]); }  
    inline void eval(int k) {  
        if(lazy[k] == Monoid::de()) return;  
        lazy[2*k]   = Monoid::h(lazy[k*2],   lazy[k]);  
        lazy[2*k+1] = Monoid::h(lazy[k*2+1], lazy[k]);  
        dat[k] = reflect(k);  
        lazy[k] = Monoid::de();  
    }  
    inline void thrust(int k) { for(int i=height;i;--i) eval(k>>i); }  
    inline void recalc(int k) { while(k>>=1) dat[k] = Monoid::f(reflect(k*2), reflect(k*2+1)); }  
  
    void update(int a, int b, E x) {  
        if(a >= b) return;  
        thrust(a+=n);  
        thrust(b+=n-1);  
        for(int l=a, r=b+1; l<r; l>>=1,r>>=1) {  
            if(l&1) lazy[l] = Monoid::h(lazy[l], x), ++l;  
            if(r&1) --r, lazy[r] = Monoid::h(lazy[r], x);  
        }  
        recalc(a);  
        recalc(b);  
    }  
    T query(int a, int b) {  
        if(a >= b) return Monoid::dt();  
        thrust(a+=n);  
        thrust(b+=n-1);  
        T vl=Monoid::dt(), vr=Monoid::dt();  
        for(int l=a, r=b+1; l<r; l>>=1,r>>=1) {  
            if(l&1) vl=Monoid::f(vl, reflect(l++));  
            if(r&1) vr=Monoid::f(reflect(--r), vr);  
        }  
        return Monoid::f(vl, vr);  
    }  
  
    friend ostream &operator <<(ostream& out,const lazysegtree<Monoid>& seg) {  
        out << "---------------------" << endl;  
        int cnt = 1;  
        for(int i=1; i<=seg.n; i*=2) {  
            REP(j, i) {  
                out << "(" << seg.dat[cnt] << "," << seg.lazy[cnt] << ") ";  
                cnt++;  
            }  
            out << endl;  
        }  
        out << "---------------------" << endl;  
        return out;  
    }  
};  
  
struct update {  
    using T = pair<PII,ll>;  
    using E = PII;  
    static T dt() { return T(PII(-1,-1), 0); }  
    static constexpr E de() { return PII(-1,-1); }  
    static T f(const T &a, const T &b) {  
        T ret;  
        ret.first = a==dt() ? b.first : a.first;   
        ret.second = a.second + b.second;  
        return ret;  
    }  
    static T g(const T &a, const E &b) {  
        T ret;  
        ret.first = b;  
        ret.second = a.second;  
        return ret;  
    }  
    static E h(const E &a, const E &b) {  
        return b;  
    }  
};  
  
struct add {  
    using T = PII;  
    using E = ll;  
    static T dt() { return PII(0, 0); }  
    static constexpr E de() { return 0; }  
    static T f(const T &a, const T &b) {  
        T ret;  
        ret.first = (a.first + b.first) % 256;  
        ret.second = a.second + b.second;  
        return ret;  
    }  
    static T g(const T &a, const E &b) {  
        T ret;  
        ret.first = (a.first + b) % 256;  
        ret.second = a.second;  
        return ret;  
    }  
    static E h(const E &a, const E &b) {  
        return (a + b) % 256;  
    }  
};  
  
int main() {  
    ll n, m, q;  
    cin >> n >> m >> q;  
    vector<ll> s(m);  
    vector<vector<ll>> x(m);  
    REP(i, m) {  
        cin >> s[i];  
        x[i].resize(s[i]);  
        REP(j, s[i]) cin >> x[i][j];  
    }  
    vector<ll> type(q), a(q), b(q), c(q);  
    REP(i, q) {  
        cin >> type[i];  
        if(type[i] == 1) cin >> a[i] >> b[i], a[i]--, b[i]--;  
        else if(type[i] == 2) cin >> a[i], a[i]--;  
        else cin >> a[i] >> b[i] >> c[i], a[i]--, b[i]--, c[i]--;  
    }  
  
    lazysegtree<update> seg0(n);  
    vector<pair<PII,ll>> ini0(n);  
    REP(i, n) {  
        ini0[i].first = PII(-1,-1);  
        ini0[i].second = 1;  
    }  
    seg0.build(ini0);  
    vector<ll> tim(q, -2);  
    REP(i, q) {  
        if(type[i] == 1) {  
            seg0.update(b[i], b[i]+s[a[i]], PII(i, i));  
        } else if(type[i] == 2) {  
            tim[i] = seg0.query(a[i], a[i]+1).first.first;  
        }  
    }  
  
    vector<ll> ans(q, -1);  
    vector<vector<ll>> eve(q);  
    REP(i, q) if(type[i] == 2) {  
        if(tim[i] != -1) eve[tim[i]].push_back(i);  
        else ans[i] = 0;  
    }  
  
    lazysegtree<update> seg(n);  
    vector<pair<PII,ll>> ini(n);  
    REP(i, n) {  
        ini[i].first = PII(-1,-1);  
        ini[i].second = 1;  
    }  
    seg.build(ini);  
  
    vector<lazysegtree<add>> seg_x(m);  
    REP(i, m) {  
        seg_x[i].init(s[i]);  
        vector<PII> v(s[i]);  
        REP(j, s[i]) v[j] = PII(x[i][j], 1);  
        seg_x[i].build(v);  
    }  
  
    vector<vector<PII>> upd(m);  
    REP(i, q) {  
        if(type[i] == 1) {  
            seg.update(b[i], b[i]+s[a[i]], PII(a[i], b[i]));  
        } else if(type[i] == 2) {  
              
        } else if(type[i] == 3) {  
            seg_x[a[i]].update(b[i], c[i]+1, 1);  
        }  
          
        for(auto j: eve[i]) {  
            auto ret = seg.query(a[j], a[j]+1).first;  
            ans[j] = seg_x[ret.first].query(a[j]-ret.second, a[j]-ret.second+1).first;  
        }  
    }  
  
    for(auto i: ans) if(i != -1) cout << i << "\n";  
  
    return 0;  
}  

G

二次元平面で縦・横方向に移動する物体が衝突 → 直線y=-x+200000上に同時に存在
あるパルスがy=-x+200000に存在するか？を管理しつつ時系列順にシミュレートする
直線に乗るタイミングは t[i]+200000-a[i] で直線から消えるタイミングは t[i]+m[i]+200000-a[i] なのでこのタイミングで直線の状態が変わる

直線から消える方・乗る方をそれぞれまとめて処理しないと変なことになるので注意

▶ソースコード(クリックで展開)

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll,ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
int main() {  
    ll n;  
    cin >> n;  
    vector<char> c(n);  
    vector<ll> t(n), m(n), a(n);  
    REP(i, n) cin >> c[i] >> t[i] >> m[i] >> a[i], t[i]--, a[i]--;  
  
    vector<vector<PII>> ts(600000);  
    REP(i, n) {  
        ts[t[i]+200000-a[i]].push_back({1, i});  
        ts[t[i]+m[i]+200000-a[i]].push_back({0, i});  
    }  
    REP(i, 600000) sort(ALL(ts[i]));  
  
    ll cnth = 0, cntv = 0, ret = 0;  
    REP(i, 600000) {  
        for(auto p: ts[i]) {  
            if(p.first == 0) {  
                if(c[p.second] == 'h') cnth--;  
                else cntv--;  
            } else {  
                if(c[p.second] == 'v') {  
                    cntv++;  
                    ret += cnth;  
                } else {  
                    cnth++;  
                    ret += cntv;  
                }  
            }  
        }  
    }  
    cout << ret << endl;  
  
    return 0;  
}