| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792751 |
2023-07-25T08:29:47 Z |
이동현(#10054) |
Binaria (CCO23_day1problem1) |
C++17 |
|
5 ms |
11988 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];
int ran[NS][3];
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]));
}
struct Fenwick{
int n;
vector<int> tr;
Fenwick(int m){
n = m + 4;
tr.resize(n);
}
void push(int pos, int val){
pos += 2;
for(int i = pos; i < n; i += (i & -i)){
tr[i] += val;
}
}
int get(int pos){
int rv = 0;
pos += 2;
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(n);
auto cant = [&]{
cout << "0\n";
exit(0);
};
queue<int> que;
for(int i = 0; i < n - k + 1; ++i){
ran[i][0] = i, ran[i][1] = i + k - 1, ran[i][2] = a[i];
que.push(i);
++isin[i];
}
auto upd = [&](int pos, int val){
assert(chk[pos] == -1);
// cout << "UPD " << pos << ' ' << val << endl;
if(val < 0 || val > 1) cant();
int low = 0, high = n - k, mid;
while(low < high){
mid = low + high + 1 >> 1;
if(ran[mid][0] <= ran[mid][1] && chk[ran[mid][1]] != -1){
int nl = fdl(ran[mid][1]);
ran[mid][2] -= tr.get(max(nl + 1, ran[mid][0]), ran[mid][1]);
ran[mid][1] = nl;
if(ran[mid][0] > ran[mid][1] && ran[mid][2]) cant();
}
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;
if(ran[mid][0] <= ran[mid][1] && chk[ran[mid][0]] != -1){
int nl = fdr(ran[mid][0]);
ran[mid][2] -= tr.get(ran[mid][0], min(nl - 1, ran[mid][1]));
ran[mid][0] = nl;
if(ran[mid][0] > ran[mid][1] && ran[mid][2]) cant();
}
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;
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;
if(chk[ran[i][0]] != -1){
int nl = fdr(ran[i][0]);
ran[i][2] -= tr.get(ran[i][0], min(nl - 1, ran[i][1]));
ran[i][0] = nl;
if(ran[i][0] > ran[i][1] && ran[i][2]) cant();
}
if(chk[ran[i][1]] != -1){
int nl = fdl(ran[i][1]);
ran[i][2] -= tr.get(max(ran[i][0], nl + 1), ran[i][1]);
ran[i][1] = nl;
if(ran[i][0] > ran[i][1] && ran[i][2]) cant();
}
if(chk[ran[i + 1][0]] != -1){
int nl = fdr(ran[i + 1][0]);
ran[i + 1][2] -= tr.get(ran[i + 1][0], min(ran[i + 1][1], nl - 1));
ran[i + 1][0] = nl;
if(ran[i + 1][0] > ran[i + 1][1] && ran[i + 1][2]) cant();
}
if(chk[ran[i + 1][1]] != -1){
int nl = fdl(ran[i + 1][1]);
ran[i + 1][2] -= tr.get(max(ran[i + 1][0], nl + 1), ran[i + 1][1]);
ran[i + 1][1] = nl;
if(ran[i + 1][0] > ran[i + 1][1] && ran[i + 1][2]) cant();
}
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] || ran[i + 1][0] > ran[i + 1][1]) continue;
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){
if(chk[ran[stval][0]] != -1){
int nl = fdr(ran[stval][0]);
ran[stval][2] -= tr.get(ran[stval][0], min(ran[stval][1], nl - 1));
ran[stval][0] = nl;
if(ran[stval][0] > ran[stval][1] && ran[stval][2]) cant();
}
if(chk[ran[stval][1]] != -1){
int nl = fdl(ran[stval][1]);
ran[stval][2] -= tr.get(max(ran[stval][0], nl + 1), ran[stval][1]);
ran[stval][1] = nl;
if(ran[stval][0] > ran[stval][1] && ran[stval][2]) cant();
}
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:94:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | mid = low + high + 1 >> 1;
| ~~~~~~~~~~~^~~
Main.cpp:112:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
112 | mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
5 ms |
11988 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
11988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
