結果

問題 No.2796 Small Matryoshka
ユーザー jay_jayjayjay_jayjay
提出日時 2024-06-28 22:22:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,040 ms / 2,000 ms
コード長 4,034 bytes
コンパイル時間 3,076 ms
コンパイル使用メモリ 200,044 KB
実行使用メモリ 152,556 KB
最終ジャッジ日時 2024-06-28 22:22:18
合計ジャッジ時間 13,076 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
b.cpp: In function 'int main()':
b.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
b.cpp:35:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]

ソースコード

diff # 

#line 1 "b.cpp"
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#line 15 "b.cpp"
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
#line 2 "/mnt/c/Users/jayja/Documents/dev/comp/lib/ds/fenwick.hpp"

#line 4 "/mnt/c/Users/jayja/Documents/dev/comp/lib/ds/fenwick.hpp"

#line 3 "/mnt/c/Users/jayja/Documents/dev/comp/lib/hash.hpp"
using namespace std;

template<typename T>
static unsigned long long splitmix64(T x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        unsigned long long y = hash<T>{}(x);
        y += 0x9e3779b97f4a7c15;
        y = (y ^ (y >> 30)) * 0xbf58476d1ce4e5b9;
        y = (y ^ (y >> 27)) * 0x94d049bb133111eb;
        return y ^ (y >> 31);
}

template<typename T>
struct splitmix {
        unsigned long long operator()(unsigned long long x) const {
                static const unsigned long long FIXED_RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
                return splitmix64(x + FIXED_RANDOM);
        }
};

unsigned long long hash_combine(unsigned long long a, unsigned long long b) {
        a ^= b + 0x517cc1b727220a95 + (a << 6) + (a >> 2);
        return a;
}

template<typename T, typename U>
struct pair_hash {
        unsigned long long operator() (const pair<T,U>& p) const {
                return splitmix<T>{}(p.first) * 69 + splitmix<U>{}(p.second);
        }
};
#line 6 "/mnt/c/Users/jayja/Documents/dev/comp/lib/ds/fenwick.hpp"

struct ft_add {
        template<typename T>
        T operator()(T a, T b) const {
                return a + b;
        }
};
struct ft_min {
        template<typename T>
        T operator()(T a, T b) const {
                return min(a, b);
        }
};
struct ft_max {
        template<typename T>
        T operator()(T a, T b) const {
                return max(a, b);
        }
};

template<typename T=long long, typename oper=ft_add>
struct fenwick // oper should be: associative, commutative, has identity
{
        int n; std::vector<T> t; T id;

        fenwick(int n, T id) : n(n), t(n, id), id(id) {}
        fenwick(int n) : fenwick(n, {}) {}
        fenwick() : fenwick(0) {}

        void resize(int n) { // UB if tree is nonzero
                this->n=n;
                t.resize(n);
        }

        void update(int i, T x) {
                for(; i<n; i|=i+1) t[i] = oper()(t[i], x);
        }

        T query(int i) {
                T x = id;
                if(i<0) return x;
                for(; ~i; i=(i&(i+1))-1) x = oper()(x, t[i]);
                return x;
        }
};

template<typename K=int, typename T=long long, typename oper=ft_add, typename H=splitmix<K>>
struct sparse_fenwick // oper should be: associative, commutative, has identity
{
        int n; __gnu_pbds::gp_hash_table<K, T, splitmix<K>> t;

        sparse_fenwick(int n) : n(n) {}
        sparse_fenwick() : sparse_fenwick(0) {}

        void resize(int n) { // UB if tree is nonzero
                this->n=n;
        }

        void update(int i, T x) {
                for(; i<n; i|=i+1) t[i] = oper()(t[i], x);
        }

        T query(int i) {
                T x = {};
                if(i<0) return x;
                for(; ~i; i=(i&(i+1))-1) x = oper()(x, t[i]);
                return x;
        }
};
#line 25 "b.cpp"
cintype in;

int main()
{
        int n=in;

        sparse_fenwick<int, int, ft_add> ft(1e9+7);
        vector<array<int,2>> pts(n);
        for(auto&[x,y]:pts)x=in,y=in, ft.update(x,1),ft.update(y,-1);
        int mx=0;
        for(auto [x,y] : pts) {
                mx=max({mx,ft.query(x),ft.query(y),ft.query(y-1)});
        }
        printf("%d\n",mx-1);
}
0