# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
74886 |
2018-09-07T09:21:03 Z |
Alexa2001 |
Fish (IOI08_fish) |
C++17 |
|
719 ms |
33652 KB |
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
const int Nmax = 5e5 + 5;
int Mod, Ans, n, i, k;
int prv[Nmax], nxt[Nmax], ord[Nmax], same[Nmax], go[Nmax], last[Nmax], F[Nmax], where[Nmax];
vector<int> Cnt, good;
struct fish
{
int len, kind;
bool operator < (const fish &other) const
{
return len < other.len;
}
} a[Nmax];
class Aint
{
int a[Nmax<<2];
public:
void build(int node, int st, int dr)
{
if(st == dr)
{
a[node] = Cnt[st-1] % Mod;
return;
}
build(left_son, st, mid);
build(right_son, mid+1, dr);
a[node] = a[left_son] * a[right_son] % Mod;
}
void query(int node, int st, int dr, int L, int R)
{
if(L <= st && dr <= R)
{
Ans *= a[node];
Ans %= Mod;
return;
}
if(L <= mid) query(left_son, st, mid, L, R);
if(mid < R) query(right_son, mid+1, dr, L, R);
}
void update(int node, int st, int dr, int pos)
{
if(st == dr)
{
--a[node];
if(a[node] == -1) a[node] = Mod-1;
return;
}
if(pos <= mid) update(left_son, st, mid, pos);
else update(right_son, mid+1, dr, pos);
a[node] = a[left_son] * a[right_son] % Mod;
}
} Weee;
int Query(int x, int y)
{
Ans = 1; x = max(x, 0); y = min(y, k-1);
if(x <= y) Weee.query(1, 1, k, x+1, y+1);
return Ans;
}
void Decr(int x)
{
Weee.update(1, 1, k, x+1);
-- Cnt[x];
}
int Search(int x)
{
int step, ans = 0;
for(step = 1; step <= k; step<<=1); step >>= 1;
for(; step; step>>=1)
if(ans + step < k && go[good[ans + step]] < x) ans += step;
return ans;
}
void solve()
{
int i, pos, ans = 0;
for(i=1; i<=n; ++i)
if(!nxt[i]) where[a[i].kind] = good.size(), good.push_back(i), Cnt.push_back(ord[i] + 1);
Weee.build(1, 1, k);
int id = k, j = n;
for(i=n; i; --i)
if(!nxt[i])
{
--id;
while(2 * a[j].len > a[i].len)
{
Decr(where[a[j].kind]);
--j;
}
if(same[i]) pos = Search(nxt[same[i]]);
else pos = Search(F[i]);
ans += Query(0, id-1) * Query(id+1, pos);
ans += Query(0, id-1) * ord[same[i]];
ans %= Mod;
}
cout << ans << '\n';
}
int main()
{
/// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
cin >> n >> k >> Mod;
for(i=1; i<=n; ++i) cin >> a[i].len >> a[i].kind;
sort(a+1, a+n+1);
for(i=1; i<=n; ++i)
{
go[i] = go[i-1];
while(2 * a[go[i] + 1].len <= a[i].len) ++ go[i];
}
for(i=1; i<=n; ++i)
{
prv[i] = last[a[i].kind];
nxt[last[a[i].kind]] = i;
last[a[i].kind] = i;
ord[i] = ord[prv[i]] + 1;
if(!prv[i]) F[i] = i;
else F[i] = F[prv[i]];
same[i] = same[prv[i]];
if(!same[i])
{
if(go[i] >= F[i]) same[i] = F[i];
else continue;
}
while(go[i] >= nxt[same[i]]) same[i] = nxt[same[i]];
}
solve();
return 0;
}
Compilation message
fish.cpp: In function 'int Search(int)':
fish.cpp:82:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(step = 1; step <= k; step<<=1); step >>= 1;
^~~
fish.cpp:82:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(step = 1; step <= k; step<<=1); step >>= 1;
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
656 KB |
Output is correct |
2 |
Correct |
2 ms |
656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
680 KB |
Output is correct |
2 |
Correct |
195 ms |
16308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
16308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
16308 KB |
Output is correct |
2 |
Correct |
110 ms |
16308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
16308 KB |
Output is correct |
2 |
Correct |
5 ms |
16308 KB |
Output is correct |
3 |
Correct |
5 ms |
16308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
16308 KB |
Output is correct |
2 |
Correct |
252 ms |
16352 KB |
Output is correct |
3 |
Incorrect |
252 ms |
23136 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
262 ms |
23136 KB |
Output is correct |
2 |
Correct |
242 ms |
23136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
23136 KB |
Output is correct |
2 |
Correct |
251 ms |
23136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
233 ms |
23136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
316 ms |
23724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
23724 KB |
Output is correct |
2 |
Correct |
392 ms |
25796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
491 ms |
26108 KB |
Output is correct |
2 |
Correct |
353 ms |
26108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
390 ms |
26108 KB |
Output is correct |
2 |
Correct |
462 ms |
26108 KB |
Output is correct |
3 |
Incorrect |
453 ms |
28284 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
606 ms |
28296 KB |
Output is correct |
2 |
Correct |
676 ms |
33180 KB |
Output is correct |
3 |
Correct |
628 ms |
33224 KB |
Output is correct |
4 |
Correct |
719 ms |
33652 KB |
Output is correct |