#720314 (C++14) No.1768 The frog in the well knows the great ocean.

提出ソース

結果

問題	No.1768 The frog in the well knows the great ocean.
ユーザー	t98slider
提出日時	2021-11-27 05:50:34
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	253 ms / 3,000 ms
コード長	12,270 bytes
コンパイル時間	2,160 ms
コンパイル使用メモリ	188,060 KB
実行使用メモリ	23,492 KB
最終ジャッジ日時	2023-09-12 09:36:28
合計ジャッジ時間	7,925 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	5 ms 4,384 KB
testcase_02	AC	5 ms 4,380 KB
testcase_03	AC	5 ms 4,384 KB
testcase_04	AC	5 ms 4,380 KB
testcase_05	AC	4 ms 4,380 KB
testcase_06	AC	216 ms 8,408 KB
testcase_07	AC	222 ms 12,356 KB
testcase_08	AC	206 ms 10,884 KB
testcase_09	AC	205 ms 8,424 KB
testcase_10	AC	208 ms 13,004 KB
testcase_11	AC	236 ms 12,856 KB
testcase_12	AC	230 ms 12,760 KB
testcase_13	AC	230 ms 12,852 KB
testcase_14	AC	231 ms 12,732 KB
testcase_15	AC	232 ms 13,008 KB
testcase_16	AC	253 ms 23,460 KB
testcase_17	AC	251 ms 23,492 KB
testcase_18	AC	251 ms 23,408 KB
testcase_19	AC	251 ms 23,428 KB
testcase_20	AC	251 ms 23,364 KB
testcase_21	AC	1 ms 4,380 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	2 ms 4,384 KB
testcase_24	AC	39 ms 4,380 KB
testcase_25	AC	234 ms 23,440 KB
testcase_26	AC	232 ms 23,460 KB
testcase_27	AC	2 ms 4,384 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define drep(i,j,n) for(int i=0;i<(int)(n-1);i++)for(int j=i+1;j<(int)(n);j++)
#define trep(i,j,k,n) for(int i=0;i<(int)(n-2);i++)for(int j=i+1;j<(int)(n-1);j++)for(int k=j+1;k<(int)(n);k++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yes(ans) if(ans)printf("yes\n");else printf("no\n")
#define Yes(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YES(ans) if(ans)printf("YES\n");else printf("NO\n")
#define popcount(v) __builtin_popcount(v)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define vector3d(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
using namespace std;
using ll = long long;
template<class T> using rpriority_queue = priority_queue<T, vector<T>, greater<T>>;
const int MOD=1000000007;
const int MOD2=998244353;
const int INF=1<<30;
const ll INF2=1LL<<60;
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T,class L>void scan(pair<T, L>& p){scan(p.first);scan(p.second);}
template<class T,class U,class V>void scan(tuple<T,U,V>& p){scan(get<0>(p));scan(get<1>(p));scan(get<2>(p));}
template<class T, size_t size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T,class L>void print(const pair<T, L>& p){print(p.first);putchar(' ');print(p.second);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll modinv(ll a, ll m) {ll b = m, u = 1, v = 0;while (b) {ll t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}
ll updivide(ll a,ll b){return (a+b-1)/b;}
template<class T> void chmax(T &a,const T b){if(b>a)a=b;}
template<class T> void chmin(T &a,const T b){if(b<a)a=b;}

namespace internal_bit{
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    int bsf(unsigned int n) {
    #ifdef _MSC_VER
        unsigned long index;
        _BitScanForward(&index, n);
        return index;
    #else
        return __builtin_ctz(n);
    #endif
    }
}
        
template <class S,
            S (*op)(S, S),
            S (*e)(),
            class F,
            S (*mapping)(F, S),
            F (*composition)(F, F),
            F (*id)()>
struct lazy_segtree {
    public:
        lazy_segtree() : lazy_segtree(0) {}
        lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
        lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal_bit::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
                update(i);
            }
        }
        void set(int p, S x) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            d[p] = x;
            for (int i = 1; i <= log; i++) update(p >> i);
        }
        S get(int p) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            return d[p];
        }
        S prod(int l, int r) {
            assert(0 <= l && l <= r && r <= _n);
            if (l == r) return e();
            l += size;
            r += size;
            for (int i = log; i >= 1; i--) {
                if (((l >> i) << i) != l) push(l >> i);
                if (((r >> i) << i) != r) push(r >> i);
            }
        S sml = e(), smr = e();
            while (l < r) {
                if (l & 1) sml = op(sml, d[l++]);
                if (r & 1) smr = op(d[--r], smr);
                l >>= 1;
                r >>= 1;
            }
            return op(sml, smr);
        }
        S all_prod() { return d[1]; }
        void apply(int p, F f) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            d[p] = mapping(f, d[p]);
            for (int i = 1; i <= log; i++) update(p >> i);
        }
        void apply(int l, int r, F f) {
            assert(0 <= l && l <= r && r <= _n);
            if (l == r) return;
            l += size;
            r += size;
            for (int i = log; i >= 1; i--) {
                if (((l >> i) << i) != l) push(l >> i);
                if (((r >> i) << i) != r) push((r - 1) >> i);
            }
            {
                int l2 = l, r2 = r;
                while (l < r) {
                    if (l & 1) all_apply(l++, f);
                    if (r & 1) all_apply(--r, f);
                    l >>= 1;
                    r >>= 1;
                }
                l = l2;
                r = r2;
            }
            for (int i = 1; i <= log; i++) {
                if (((l >> i) << i) != l) update(l >> i);
                if (((r >> i) << i) != r) update((r - 1) >> i);
            }
            }
        template <bool (*g)(S)> int max_right(int l) {
            return max_right(l, [](S x) { return g(x); });
        }
        template <class G> int max_right(int l, G g) {
            assert(0 <= l && l <= _n);
            assert(g(e()));
            if (l == _n) return _n;
            l += size;
            for (int i = log; i >= 1; i--) push(l >> i);
            S sm = e();
            do {
                while (l % 2 == 0) l >>= 1;
                if (!g(op(sm, d[l]))) {
                    while (l < size) {
                        push(l);
                        l = (2 * l);
                        if (g(op(sm, d[l]))) {
                            sm = op(sm, d[l]);
                            l++;
                        }
                    }
                    return l - size;
                }
                sm = op(sm, d[l]);
                l++;
            } while ((l & -l) != l);
            return _n;
        }
        template <bool (*g)(S)> int min_left(int r) {
            return min_left(r, [](S x) { return g(x); });
        }
        template <class G> int min_left(int r, G g) {
            assert(0 <= r && r <= _n);
            assert(g(e()));
            if (r == 0) return 0;
            r += size;
            for (int i = log; i >= 1; i--) push((r - 1) >> i);
            S sm = e();
            do {
                r--;
                while (r > 1 && (r % 2)) r >>= 1;
                if (!g(op(d[r], sm))) {
                    while (r < size) {
                        push(r);
                        r = (2 * r + 1);
                        if (g(op(d[r], sm))) {
                            sm = op(d[r], sm);
                            r--;
                        }
                    }
                    return r + 1 - size;
                }
                sm = op(d[r], sm);
            } while ((r & -r) != r);
            return 0;
        }
    private:
        int _n, size, log;
        std::vector<S> d;
        std::vector<F> lz;
        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
        void all_apply(int k, F f) {
            d[k] = mapping(f, d[k]);
            if (k < size) lz[k] = composition(f, lz[k]);
        }
        void push(int k) {
            all_apply(2 * k, lz[k]);
            all_apply(2 * k + 1, lz[k]);
            lz[k] = id();
        }
};

using S=int;
using F=int;
//単位元
S e2(){return 0;}
//演算
S op2(S l,S r){return max(l,r);}
//xにfを作用させた時の値の変化
S mapping(F f,S x){return max(x,f);}
//gを演算した後にfを演算させると演算子はどうなるか
F composition(F f, F g){return max(f,g);}
//作用させても変化させないもの
F id(){return 0;}

template<class T,T (*op)(T, T),T (*e)()> struct SparseTable {
    vector<vector<T>> table;
    vector<int> lookup;
    int LOGV=0, _n;
    SparseTable(const vector<T> &v) {
        _n=v.size();
        while(_n>>LOGV)LOGV++;
        table.assign(LOGV,vector<T>(_n));
        lookup.resize(_n+1);
        for(int i = 0; i < _n; i++) table[0][i] = v[i];
        for(int i = 1; i < LOGV; i++) {
            for(int j = 0; j + (1 << i) <= _n; j++) {
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
        lookup[1]=0;
        for(int i = 2; i < lookup.size(); i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }
    T prod(const int l, const int r){
        assert(0 <= l && l <= r && r <= _n);
        if(l==r)return e();
        int b = lookup[r - l];
        return op(table[b][l],table[b][r - (1<<b)]);
    }
};

int op(int a,int b){return min(a,b);}
int e(){return INF;}

void solve(vector<int> &a,vector<int> &b){
    int n=a.size();
    if(*max_element(all(b))>*max_element(all(a))){
        out("No");
        return;
    }
    if(*min_element(all(b))<*min_element(all(a))){
        out("No");
        return;
    }
    vector<pair<int,int>> p(n);
    bool h=false;
    rep(i,n){
        p[i].first=a[i];
        p[i].second=i;
        if(b[i]<a[i]){
            h=true;
            break;
        }
    }
    if(h){
        out("No");
        return;
    }
    sort(all(p));
    int j=0;
    while(j<p.size()){
        queue<int> next;
        int pre=j;
        while(j<p.size()&&p[j].first==p[pre].first){
            next.push(p[j].second);
            j++;
        }
        while(!next.empty()){
            int x=next.front();
            next.pop();
            if(x-1>=0){
                if(a[x-1]!=b[x-1]&&a[x]>a[x-1]){
                    a[x-1]=a[x];
                    next.push(x-1);
                }
            }
            if(x+1<n){
                if(a[x+1]!=b[x+1]&&a[x]>a[x+1]){
                    a[x+1]=a[x];
                    next.push(x+1);
                }
            }
        }
    }
    Yes(a==b);
}

int main(){
    codefor{
        INT(n);
        vector<int> a(n),b(n);
        in(a,b);
        if(n<=5000){
            solve(a,b);
            continue;
        }
        SparseTable<int,op,e> st(b);
        lazy_segtree<S, op2, e2, F, mapping, composition, id> seg(a);
        rep(i,n){
            if(a[i]>b[i])break;
            int l=0,r=n+1,mid;
            while(l<r){
                mid=(l+r)/2;
                if(i+mid<=n&&st.prod(i,i+mid)>=a[i])l=mid+1;
                else r=mid;
            }
            seg.apply(i,i+l-1,a[i]);
            l=0,r=n+1;
            while(l<r){
                mid=(l+r)/2;
                if(i+1-mid>=0&&st.prod(i+1-mid,i+1)>=a[i])l=mid+1;
                else r=mid;
            }
            seg.apply(i+1-(l-1),i+1,a[i]);
        }
        vector<int> c(n);
        rep(i,n)c[i]=seg.get(i);
        Yes(c==b);
    }
}

yukicoder

結果

テストケース

ソースコード