QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#620564 | #8527. Power Divisions | badminton | WA | 2384ms | 101556kb | C++14 | 3.2kb | 2024-10-07 19:15:22 | 2024-10-07 19:15:23 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
template<class X, class Y>
bool minz(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} return false;
}
template<class X, class Y>
bool maxz(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
const int N = 1e6 + 50;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
ll rd (ll l, ll r){
ll res = 0;
for (int i = 0; i < 4; i++)
res = (res << 15) ^ rand();
return res;
}
void add (ll &u, ll v){
u += v;
if (u >= mod)
u -= mod;
}
ll a[N], n, cur, pre[N], pw[N];
ll dp[N], mn, mx;
map <int, int> bit;
void addbit (int x){
cur ^= pw[x];
bit[x]++;
minz(mn, x);
while (bit[x] > 1){
bit[x] -= 2;
if (mn == x)
mn++;
bit[++x]++;
cur ^= pw[x];
}
maxz(mx, x);
}
void solve (int l, int r){
if (l == r){
add(dp[l], dp[l - 1]);
//cout <<l << " " << r << " " << dp[l] << " zz\n";
return;
}
int mid = (l + r) >> 1;
solve(l, mid);
map <ll, ll> g, f;
cur = 0;
mn = mx = a[mid];
bit.clear();
//cout << l << " " << r << ":\n";
ford (i, mid, l){
addbit(a[i]);
add(f[cur], dp[i - 1]);
ll x = pre[mx] ^ (mn == 0 ? 0 : pre[mn - 1]) ^ pw[mn] ^ cur;
if (x != cur)
add(g[x], dp[i - 1]);
//cout << i << " " << mid << " " << mn << " " << mx << " " << cur << " " << x << " " << dp[i - 1] << "\n";
}
//cout << "--\n";
cur = 0;
mn = mx = a[mid + 1];
bit.clear();
forr (i, mid + 1, r){
addbit(a[i]);
ll x = pre[mx] ^ (mn == 0 ? 0 : pre[mn - 1]) ^ pw[mn] ^ cur;
add(dp[i], g[cur]);
add(dp[i], f[x]);
//cout << mid + 1 << " " << i << " " << mn << " " << mx << " " << cur << " " << dp[i] << "\n";
//cout << x << " " << pre[mx] << " " << pw[mx] << "\n";
}
solve(mid + 1, r);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef hqm
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
srand(time(NULL));
cin >> n;
forr (i, 1, n){
cin >> a[i];
}
pw[0] = pre[0] = rand();
forr (i, 1, 1000030){
pw[i] = rand();
pre[i] = pre[i - 1] ^ pw[i];
}
dp[0] = 1;
solve(1, n);
forr (i, 0, n){
//cout << dp[i] << " " << pw[i] << "\n";
}
cout << dp[n] << "\n";
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 20028kb
input:
5 2 0 0 1 1
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 20108kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 9ms
memory: 22360kb
input:
2 1 1
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 8ms
memory: 20020kb
input:
3 2 1 1
output:
3
result:
ok 1 number(s): "3"
Test #5:
score: 0
Accepted
time: 5ms
memory: 22160kb
input:
4 3 2 2 3
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 3ms
memory: 22100kb
input:
5 3 4 4 2 4
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 5ms
memory: 22384kb
input:
7 3 4 3 5 6 3 4
output:
6
result:
ok 1 number(s): "6"
Test #8:
score: 0
Accepted
time: 8ms
memory: 22124kb
input:
10 8 6 5 6 7 8 6 8 9 9
output:
4
result:
ok 1 number(s): "4"
Test #9:
score: 0
Accepted
time: 4ms
memory: 22084kb
input:
96 5 1 0 2 5 5 2 4 2 4 4 2 3 4 0 2 1 4 3 1 2 0 2 2 3 2 4 5 3 5 2 0 2 2 5 3 0 4 5 3 5 4 4 3 1 2 0 5 4 5 0 2 3 2 4 0 0 4 2 0 2 5 3 3 1 5 5 1 1 1 0 5 0 3 0 2 1 1 0 5 0 3 3 4 4 5 3 0 2 2 0 5 4 5 0 5
output:
11332014
result:
ok 1 number(s): "11332014"
Test #10:
score: 0
Accepted
time: 10ms
memory: 20188kb
input:
480 2 0 4 4 1 0 0 3 1 1 4 2 5 5 4 2 1 2 4 4 1 3 4 3 0 5 2 0 2 5 1 0 5 0 0 5 5 0 2 5 2 2 3 1 4 3 5 4 5 2 4 4 4 4 1 4 0 3 4 3 4 1 0 4 3 4 5 4 3 5 0 2 2 0 1 5 4 4 2 0 3 3 3 4 3 0 5 5 3 1 5 1 0 1 0 4 3 0 5 1 4 1 4 3 0 1 3 5 0 3 3 1 0 4 1 1 2 0 1 2 0 3 5 2 0 5 5 5 5 3 5 1 0 2 5 2 2 0 2 0 2 3 5 1 2 1 5 4 ...
output:
506782981
result:
ok 1 number(s): "506782981"
Test #11:
score: 0
Accepted
time: 10ms
memory: 22700kb
input:
2400 0 2 2 0 5 4 3 2 3 2 5 4 5 4 4 5 2 2 4 2 2 0 1 0 5 0 4 4 0 0 5 0 4 0 1 3 4 5 0 3 1 0 4 0 2 5 0 3 3 3 3 1 0 5 5 3 1 3 5 2 4 0 5 0 4 5 4 2 2 1 5 2 2 4 1 0 5 1 5 0 1 2 0 0 3 5 4 0 0 1 1 1 4 2 0 5 1 3 3 5 0 4 4 1 5 5 3 4 4 4 0 2 4 0 5 1 3 1 5 0 5 5 1 3 0 3 1 2 0 1 1 3 5 2 3 4 0 3 0 5 4 0 4 3 5 0 5 2...
output:
586570528
result:
ok 1 number(s): "586570528"
Test #12:
score: 0
Accepted
time: 47ms
memory: 22916kb
input:
12000 2 2 1 2 0 2 5 3 2 0 1 3 2 5 4 0 0 5 3 2 0 2 3 4 3 2 1 4 3 0 3 5 4 1 0 2 4 1 3 2 3 5 0 3 0 0 4 0 4 5 1 0 4 1 1 1 5 4 3 0 3 5 4 5 2 5 0 1 2 3 5 5 2 5 4 2 0 4 4 3 0 0 2 5 0 3 4 2 5 4 2 1 4 5 1 1 2 3 0 3 3 3 3 4 0 5 3 4 0 3 0 2 0 0 2 0 3 4 2 2 0 1 0 5 3 0 2 0 2 2 1 0 5 3 5 4 5 5 0 4 0 4 1 4 4 3 2 ...
output:
201653965
result:
ok 1 number(s): "201653965"
Test #13:
score: 0
Accepted
time: 272ms
memory: 36376kb
input:
60000 2 5 0 3 2 3 5 3 5 5 4 1 1 5 3 0 1 1 2 5 5 5 0 3 2 0 3 2 3 3 0 0 1 4 3 1 4 2 3 3 0 5 1 0 1 1 5 5 4 0 5 4 1 3 1 3 5 3 2 4 4 4 5 4 3 2 3 2 4 5 2 0 4 5 1 2 0 4 0 5 1 3 4 1 2 4 1 1 3 3 0 1 1 3 0 0 2 3 3 2 1 4 1 2 4 3 3 5 2 5 3 4 3 0 2 1 1 1 5 1 2 4 2 3 1 2 1 0 2 0 1 1 5 5 3 4 2 5 2 4 5 3 0 5 1 4 2 ...
output:
592751350
result:
ok 1 number(s): "592751350"
Test #14:
score: 0
Accepted
time: 1915ms
memory: 95848kb
input:
300000 0 5 1 5 5 4 5 3 0 5 0 5 1 4 1 2 2 2 3 0 1 5 4 0 3 1 4 5 2 1 0 3 2 1 2 5 0 2 4 5 0 1 2 1 1 0 0 5 3 0 0 3 4 5 0 2 1 1 1 2 5 1 4 3 1 0 2 0 0 4 3 3 2 5 3 3 1 5 2 0 2 4 3 1 0 3 4 1 3 3 1 0 0 1 1 1 3 1 2 3 5 3 3 2 0 3 0 0 5 5 0 0 0 0 1 4 3 3 4 3 4 5 3 3 5 1 1 4 2 2 1 3 2 1 1 0 0 5 5 0 0 3 2 4 5 5 2...
output:
842503795
result:
ok 1 number(s): "842503795"
Test #15:
score: 0
Accepted
time: 1158ms
memory: 64256kb
input:
300000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
432100269
result:
ok 1 number(s): "432100269"
Test #16:
score: 0
Accepted
time: 1134ms
memory: 61960kb
input:
300000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000...
output:
432100269
result:
ok 1 number(s): "432100269"
Test #17:
score: 0
Accepted
time: 1407ms
memory: 72492kb
input:
299995 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0...
output:
261818019
result:
ok 1 number(s): "261818019"
Test #18:
score: 0
Accepted
time: 2011ms
memory: 101124kb
input:
299997 2 2 0 9 4 4 2 3 8 9 3 9 1 6 4 0 1 5 1 0 7 9 3 3 8 9 3 8 3 6 9 3 9 5 9 1 4 4 7 5 9 0 7 3 7 2 0 3 3 8 2 1 7 6 8 1 6 1 8 4 7 6 3 6 1 6 8 9 3 8 1 5 0 8 1 10 0 3 4 5 8 5 6 9 2 4 5 0 9 0 9 5 1 0 3 7 5 8 8 10 10 3 3 10 5 8 9 9 7 4 4 1 1 6 5 7 2 5 8 3 3 9 6 4 1 0 2 6 2 8 7 7 10 5 7 8 3 8 5 1 6 6 6 1 ...
output:
999738318
result:
ok 1 number(s): "999738318"
Test #19:
score: -100
Wrong Answer
time: 2384ms
memory: 101556kb
input:
299999 97 34 33 30 15 73 31 69 60 63 79 87 78 13 49 58 23 38 91 28 70 70 14 98 56 59 81 66 29 21 10 51 94 32 41 98 16 48 67 62 55 5 17 81 30 91 39 93 73 74 46 74 41 99 19 10 0 16 72 95 84 40 97 17 76 10 42 50 66 97 4 30 71 74 46 5 75 87 55 82 38 94 14 82 49 10 23 21 19 99 52 100 71 29 64 73 54 88 2 ...
output:
698456106
result:
wrong answer 1st numbers differ - expected: '799664563', found: '698456106'