| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792769 |
2023-07-25T08:36:17 Z |
이동현(#10054) |
Binaria (CCO23_day1problem1) |
C++17 |
|
6 ms |
12060 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int NS = (int)1e6 + 4, mod = (int)1e6 + 3;
int n, k;
int a[NS];
int r[NS], l[NS], chk[NS], isin[NS];
long long pw(int x, int y){
if(!y) return 1;
if(y == 1) return x;
int v = pw(x, y / 2);
return (long long)v * v % mod * (y % 2 ? x : 1) % mod;
}
int fdr(int x){
return (x == r[x] ? x : r[x] = fdr(r[x]));
}
int fdl(int x){
return (x == l[x] || x == -1 ? x : l[x] = fdl(l[x]));
}
int tr[NS];
struct Fenwick{
Fenwick(){}
void push(int pos, int val){
pos += 5;
for(int i = pos; i < n + 10; i += (i & -i)){
tr[i] += val;
}
}
int get(int pos){
int rv = 0;
pos += 5;
for(int i = pos; i > 0; i -= (i & -i)){
rv += tr[i];
}
return rv;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
iota(r, r + NS, 0);
iota(l, l + NS, 0);
memset(chk, -1, sizeof(chk));
int n, k;
cin >> n >> k;
vector<int> a(n - k + 1);
for(int i = 0; i < n - k + 1; ++i){
cin >> a[i];
}
Fenwick tr;
auto cant = [&]{
cout << "0\n";
exit(0);
};
auto nor = [&](vector<int>&x){
if(x[0] > x[1]) return;
int nl = fdr(x[0]);
int nr = fdl(x[1]);
if(nl > nr){
int nv = x[2] - tr.get(x[0], x[1]);
if(nv) cant();
x[0] = nl, x[1] = nr, x[2] = 0;
}
int nv = x[2] - tr.get(x[0], nl - 1) - tr.get(nr + 1, x[1]);
x[0] = nl, x[1] = nr, x[2] = nv;
};
queue<int> que;
vector<vector<int>> ran(n - k + 1);
for(int i = 0; i < n - k + 1; ++i){
ran[i] = {i, i + k - 1, a[i]};
que.push(i);
++isin[i];
}
auto upd = [&](int pos, int val){
if(val < 0 || val > 1) cant();
int low = 0, high = n - k, mid;
while(low < high){
mid = low + high + 1 >> 1;
nor(ran[mid]);
if(ran[mid][1] < pos){
low = mid;
}
else{
high = mid - 1;
}
}
if(!isin[low]) que.push(low), ++isin[low];
low = 0, high = n - k;
while(low < high){
mid = low + high >> 1;
nor(ran[mid]);
if(ran[mid][0] > pos){
high = mid;
}
else{
low = mid + 1;
}
}
if(!isin[low]) que.push(low), ++isin[low];
chk[pos] = val;
tr.push(pos, val);
l[pos] = pos - 1;
r[pos] = pos + 1;
};
int rep = 0;
while(!que.empty()){
++rep;
assert(rep <= n * 6);
int i = que.front();
--isin[i];
que.pop();
if(i < 0 || i >= n - k || ran[i][0] > ran[i][1] || ran[i + 1][0] > ran[i + 1][1]) continue;
nor(ran[i]);
nor(ran[i + 1]);
if(ran[i][0] > ran[i][1] || ran[i + 1][0] > ran[i + 1][1]) continue;
int sval = ran[i][2] - tr.get(ran[i][0], ran[i][1]);
int nval = ran[i + 1][2] - tr.get(ran[i + 1][0], ran[i + 1][1]);
if(ran[i][0] == ran[i + 1][0] && ran[i][1] == ran[i + 1][1]){
if(sval != nval) cant();
continue;
}
if(ran[i][0] < ran[i + 1][0] && ran[i][1] < ran[i + 1][1] && sval == nval){
continue;
}
if(!isin[i + 1]) que.push(i + 1), ++isin[i + 1];
if(i && !isin[i - 1]) que.push(i - 1), ++isin[i - 1];
if(ran[i][0] == ran[i + 1][0]){
upd(ran[i + 1][1], nval - sval);
}
else if(ran[i][1] == ran[i + 1][1]){
upd(ran[i][0], sval - nval);
}
else{
if(sval > nval){
upd(ran[i][0], sval - nval);
upd(ran[i + 1][1], 0);
}
else{
upd(ran[i + 1][1], nval - sval);
upd(ran[i][0], 0);
}
}
}
int stval = 0;
while(stval < n - k + 1){
nor(ran[stval]);
if(ran[stval][0] <= ran[stval][1]) break;
++stval;
}
if(stval == n - k + 1){
cout << "1\n";
return 0;
}
int ac = 0, oc = a[stval];
assert(stval + k <= n);
for(int i = stval; i < stval + k; ++i){
ac += (chk[i] == -1);
oc -= (chk[i] == 1);
}
long long ans = 1;
for(int i = oc + 1; i <= ac; ++i){
(ans *= i) %= mod;
}
for(int i = 2; i <= ac - oc; ++i){
(ans *= pw(i, mod - 2)) %= mod;
}
cout << ans << '\n';
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:102:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | mid = low + high + 1 >> 1;
| ~~~~~~~~~~~^~~
Main.cpp:115:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12060 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12060 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12060 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12060 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12060 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
12060 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
