| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 74879 |
2018-09-07T09:01:25 Z |
Alexa2001 |
Fish (IOI08_fish) |
C++17 |
|
650 ms |
66560 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];
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];
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:81:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(step = 1; step <= k; step<<=1); step >>= 1;
^~~
fish.cpp:81: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 |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
652 KB |
Output is correct |
| 2 |
Correct |
208 ms |
22416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
22416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22416 KB |
Output is correct |
| 2 |
Correct |
107 ms |
22416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22416 KB |
Output is correct |
| 2 |
Correct |
6 ms |
22416 KB |
Output is correct |
| 3 |
Correct |
6 ms |
22416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
26080 KB |
Output is correct |
| 2 |
Incorrect |
255 ms |
39124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
312 ms |
45096 KB |
Output is correct |
| 2 |
Correct |
251 ms |
52184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
52184 KB |
Output is correct |
| 2 |
Correct |
250 ms |
63568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
238 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
324 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
254 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
580 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
650 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
