結果

問題 No.3313 Matryoshka
コンテスト
ユーザー t98slider
提出日時 2025-10-25 13:50:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,454 bytes
コンパイル時間 1,906 ms
コンパイル使用メモリ 213,432 KB
実行使用メモリ 176,556 KB
最終ジャッジ日時 2025-10-25 13:51:10
合計ジャッジ時間 13,326 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// 壊れてるけど順列ならいける
template <class S, S (*op)(S, S), S (*e)()> struct segtree2D_lite {
    int H , h;
    std::vector<int> W;
    std::vector<std::vector<int>> pos;
    std::vector<tuple<int, int, S>> preorder;
    std::vector<std::vector<S>> d;
    segtree2D_lite(int Ymax) : h(Ymax+1) {
        H = 1 << ceil_pow2(h);
        W.resize(2*H, 0), pos.resize(2*H), d.resize(2*H);
    }
    void preset(int y, int x, S v = e()){
        assert(0 <= y && y < h);
        if(v != e())preorder.emplace_back(y,x,v);
        y += H;
        while(y){
            pos[y].push_back(x);
            y >>= 1;
        }
    }
    void build(){
        for(int y = 2*H - 1 ; y >= 1 ; y--){
            std::sort(pos[y].begin(), pos[y].end());
            pos[y].erase(std::unique(pos[y].begin(), pos[y].end()), pos[y].end());
            W[y] = 1 << ceil_pow2(pos[y].size()) ;
            d[y].resize(2 * W[y] , e());
        }
        for(int i = 0; i < int(preorder.size()) ; i++){
            set(std::get<0>(preorder[i]), std::get<1>(preorder[i]), std::get<2>(preorder[i]));
        }
    }
    void set(int py, int px, S v){
        assert(0 <= py && py < h);
        int y = py + H;
        while(y){
            int x = std::lower_bound(pos[y].begin(), pos[y].end(), px) - pos[y].begin();
            x += W[y];
            d[y][x] = v;
            x >>= 1;
            while(x){
                updateX(y, x);
                x >>= 1;
            }
            y >>= 1;
        }
    }
    S get(int py, int px){
        assert(0 <= py && py < h);
        int y = py + H;
        int x = std::lower_bound(pos[y].begin(), pos[y].end(), px) - pos[y].begin();
        return d[y][x + W[y]];
    }
    S prod(int lpy, int lpx , int rpy , int rpx){
        assert(0 <= lpy && lpy <= rpy && rpy <= h);
        assert(lpx <= rpx);
        S sml = e(), smr = e();
        int ly = lpy + H, ry = rpy + H ;
        while (ly < ry) {
            if (ly & 1) sml = op(sml, yline_prod(lpx, rpx , ly++));
            if (ry & 1) smr = op(yline_prod(lpx, rpx , --ry), smr);
            ly >>= 1, ry >>= 1;
        }
        return op(sml, smr);
    }
    S yline_prod(int lpx, int rpx , int y){
        int lx = std::lower_bound(pos[y].begin(), pos[y].end(), lpx) - pos[y].begin();
        int rx = std::lower_bound(pos[y].begin(), pos[y].end(), rpx) - pos[y].begin();
        S sml = e(), smr = e();
        lx += W[y], rx += W[y] ;
        while (lx < rx) {
            if (lx & 1) sml = op(sml, d[y][lx++]);
            if (rx & 1) smr = op(d[y][--rx], smr);
            lx >>= 1, rx >>= 1;
        }
        return op(sml, smr);
    }
    private:
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    void updateX(int yi, int xi) { d[yi][xi] = op(d[yi][2 * xi], d[yi][2 * xi + 1]); }
};

int op(int lhs, int rhs){return lhs + rhs;}
constexpr int e(){return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    segtree2D_lite<int, op, e> seg(1000000);
    for(auto &&[l, r] : a){
        cin >> l >> r;
        l--, r--;
        seg.preset(l, r);
    }
    seg.build();
    long long ans = 0;
    for(int i = n - 1; i >= 0; i--){
        auto [l, r] = a[i];
        ans += seg.prod(l, l, r, r);
        seg.set(l, r, 1);
    }
    cout << ans << '\n';
}
0