結果

問題 No.3313 Matryoshka
コンテスト
ユーザー GOTKAKO
提出日時 2025-10-24 22:39:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,385 bytes
コンパイル時間 2,502 ms
コンパイル使用メモリ 216,396 KB
実行使用メモリ 277,204 KB
最終ジャッジ日時 2025-10-24 22:40:00
合計ジャッジ時間 9,599 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using SS = int;
class SegmentTree2D{ //二次元セグ木 計算量O(logH*logW) メモリO(2H+N).
    private:
    using Typepos = int;
    class DynamicSegmentTree{ //動的再帰セグ木 二分探索はない.
        public:
        SS op(SS a,SS b){return a+b;}
        static inline const SS e = 0;
 
        private:
        struct Node{
            Typepos pos; //葉posの頂点.
            SS v,all; //v->posの値,all->部分木全部.
            Node *LR[2]; //二分木.
            Node(Typepos p,SS vv):pos(p),v(vv),all(vv),LR{nullptr,nullptr}{}
        };
        Node *root;
        public:
        Typepos siz = 1<<30;
        DynamicSegmentTree(){root = nullptr;}
        void make(Typepos N){siz = 1; while(siz < N) siz *= 2;}
        void setsiz(Typepos N){assert(N==(N&-N)); siz = N;}
 
        private:
        SS getval(Node *p){return p?p->all:e;} //ノードpのallを返す. nullptrの場合分け省く用.
        //葉でない[a,b)の頂点にも[a,b)の1つを割り振ることにより空間をO(N)にする 適宜割り振る所は更新.
        Node* update(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-op(p,v); 更新する.
            if(p == nullptr) return new Node(pos,v);
            if(p->pos == pos){
                p->v = op(p->v,v);
                p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
                return p;
            }
            Typepos m = (a+b)/2;
            if(pos < m){
                if(pos > p->pos) swap(pos,p->pos),swap(v,p->v);//左の子のposは親のposより小さくする.
                p->LR[0] = update(a,m,pos,p->LR[0],v);
            }
            else{
                if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく.
                p->LR[1] = update(m,b,pos,p->LR[1],v);
            }
            p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
            return p;
        }
        Node* set(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-v　設定する.
            if(p == nullptr) return new Node(pos,v);
            if(p->pos == pos){
                p->v = v;
                p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
                return p;
            }
            Typepos m = (a+b)/2;
            if(pos < m){
                if(pos > p->pos) swap(pos,p->pos),swap(v,p->v); //左の子のposは親のposより小さくする.
                p->LR[0] = set(a,m,pos,p->LR[0],v);
            }
            else{
                if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく.
                p->LR[1] = set(m,b,pos,p->LR[1],v);
            }
            p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1])));
            return p;
        }
        public:
        void update(Typepos pos,SS x){
            assert(0 <= pos && pos < siz);
            root = update(0,siz,pos,root,x);
        }
        void set(Typepos pos,SS x){
            assert(0 <= pos && pos < siz);
            root = set(0,siz,pos,root,x);
        }
        private:
        SS findans(Typepos L,Typepos R,Typepos a,Typepos b,Node *p){
            if(p == nullptr || R <= a || b <= L) return e;
            if(L <= a && b <= R) return p->all;
            Typepos m = (a+b)/2;
            SS ret = findans(L,R,a,m,p->LR[0]);
            if(L <= p->pos && p->pos < R) ret = op(ret,p->v);
            return op(ret,findans(L,R,m,b,p->LR[1]));
        }
        public:
        SS rangeans(Typepos L,Typepos R){
            assert(0 <= L && L <= siz && 0 <= R && R <= siz); // L>Rは許容する.
            if(L >= R) return e; 
            return findans(L,R,0,siz,root);
        }
        SS allrange(){return getval(root);}
        SS get(Typepos pos){return rangeans(pos,pos+1);} //O(logsiz).
    };
 
    int h = 1; Typepos w = 1;
    vector<DynamicSegmentTree> dat;
    public:
    SegmentTree2D(int H,Typepos W){
        h = 1,w = 1;
        while(h < H) h <<= 1;
        while(w < W) w <<= 1;
        dat.resize(h*2);
        for(auto &d : dat) d.setsiz(w);
    }
    void update(int x,Typepos y,SS v){ //(x,y)にvを加える.
        assert(0 <= x && x < h && 0 <= y && y < w);
        x += h;
        while(x > 0) dat.at(x).update(y,v),x >>= 1;
    }
    void set(int x,Typepos y,SS v){ //(x,y)をvにする.
        assert(0 <= x && x < h && 0 <= y && y < w);
        x += h;
        while(x > 0) dat.at(x).set(y,v),x >>= 1;
    }
    SS rangeans(int x1,int x2,Typepos y1,Typepos y2){ //(x1,y1)~(x2,y2)の区間の総和.
        assert(0 <= min(x1,x2) && max(x1,x2) <= h && 0 <= min(y1,y2) && max(y1,y2) <= w); //x1>x2,y1>y2はok.
        x1 += h,x2 += h;
        SS ret = dat.at(0).e;
        while(x1 < x2){
            if(x1&1) ret = dat.at(0).op(ret,dat.at(x1++).rangeans(y1,y2));
            if(x2&1) ret = dat.at(0).op(dat.at(--x2).rangeans(y1,y2),ret);
            x1 >>= 1; x2 >>= 1;
        }
        return ret;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N; cin >> N;
    SegmentTree2D Z(1000000,1000000);
    vector<pair<int,int>> LR(N);
    for(auto &[l,r] : LR) cin >> l >> r,l--;
    long long answer = 0;
    for(int i=N; i--;){
        auto [l,r] = LR.at(i);
        answer += Z.rangeans(l,r,l,r);
        Z.update(l,r,1);
    }

    cout << answer << endl;
}
0