Submission #58042

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//header{{{
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7;
constexpr int MOD = 998244353;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}
//SegmentTree{{{
template< typename Monoid >
struct SegmentTree {
using F = function< Monoid(Monoid, Monoid) >;
int sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[a]);
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
//}}}
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int N,K;
cin >> N >> K;
SegmentTree<int> seg(N, [](int a,int b){ return a & b; },(1ll << 62) -1);
rep(i,N){
int x;
cin >> x;
seg.update(i,x);
}
auto isOK = [&](int l){
for(int i = 0;i + l <= N;++i){
if(seg.query(i,i+l) > K) return true;
}
return false;
};
int low = 0,high = N+1;
while(high - low > 1){
int mid = (high + low) / 2;
if(isOK(mid)) low = mid;
else high = mid;
}
cout << (low == 0 ? -1 : low) << '\n';
return 0;
}

ステータス

項目 データ
問題 1254 - AND AND AND...
ユーザー名 ei1903
投稿日時 2020-01-08 23:16:40
言語 C++14
状態 Accepted
得点 10
ソースコード長 3877 Byte
最大実行時間 94 ms
最大メモリ使用量 2904 KB

セット

セット 得点 Cases
1 ALL 10 / 10 in*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 94 ms 2652 KB
1
in02.txt AC 78 ms 2728 KB
1
in03.txt AC 78 ms 2544 KB
1
in04.txt AC 82 ms 2620 KB
1
in05.txt AC 79 ms 2568 KB
1
in06.txt AC 87 ms 2644 KB
1
in07.txt AC 88 ms 2720 KB
1
in08.txt AC 87 ms 2532 KB
1
in09.txt AC 82 ms 2608 KB
1
in10.txt AC 90 ms 2684 KB
1
in11.txt AC 89 ms 2508 KB
1
in12.txt AC 81 ms 2584 KB
1
in13.txt AC 87 ms 2532 KB
1
in14.txt AC 80 ms 2608 KB
1
in15.txt AC 83 ms 2552 KB
1
in16.txt AC 84 ms 2628 KB
1
in17.txt AC 80 ms 2572 KB
1
in18.txt AC 87 ms 2648 KB
1
in19.txt AC 80 ms 2596 KB
1
in20.txt AC 83 ms 2672 KB
1
in21.txt AC 83 ms 2748 KB
1
in22.txt AC 83 ms 2564 KB
1
in23.txt AC 83 ms 2768 KB
1
in24.txt AC 88 ms 2716 KB
1
in25.txt AC 84 ms 2788 KB
1
in26.txt AC 83 ms 2732 KB
1
in27.txt AC 85 ms 2804 KB
1
in28.txt AC 80 ms 2616 KB
1
in29.txt AC 75 ms 2560 KB
1
in30.txt AC 89 ms 2632 KB
1
in31.txt AC 84 ms 2576 KB
1
in32.txt AC 36 ms 2904 KB
1
in33.txt AC 38 ms 2728 KB
1
in34.txt AC 33 ms 2680 KB
1
in35.txt AC 32 ms 2628 KB
1
in36.txt AC 34 ms 2708 KB
1
in37.txt AC 31 ms 2780 KB
1
in38.txt AC 33 ms 2728 KB
1
in39.txt AC 31 ms 2804 KB
1
in40.txt AC 31 ms 2748 KB
1
in41.txt AC 32 ms 2824 KB
1
in42.txt AC 39 ms 2648 KB
1
in43.txt AC 38 ms 2724 KB
1
in44.txt AC 46 ms 2668 KB
1
in45.txt AC 33 ms 2748 KB
1
in46.txt AC 44 ms 2568 KB
1
in47.txt AC 37 ms 2772 KB
1
in48.txt AC 93 ms 2724 KB
1
in49.txt AC 61 ms 2672 KB
1
in50.txt AC 40 ms 2752 KB
1
in51.txt AC 78 ms 2704 KB
1
in52.txt AC 85 ms 2780 KB
1
in53.txt AC 31 ms 2860 KB
1
in54.txt AC 33 ms 2808 KB
1
in55.txt AC 22 ms 840 KB
1
in56.txt AC 27 ms 804 KB
1
in57.txt AC 20 ms 760 KB
1
in58.txt AC 90 ms 2756 KB
1
in59.txt AC 84 ms 2828 KB
1
in60.txt AC 90 ms 2900 KB
1
in61.txt AC 40 ms 2844 KB
1
in62.txt AC 34 ms 2796 KB
1
sample01.txt AC 32 ms 696 KB
sample02.txt AC 20 ms 776 KB
sample03.txt AC 24 ms 728 KB