# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
363486 |
2021-02-06T08:42:03 Z |
hivakarami |
Fish (IOI08_fish) |
C++14 |
|
779 ms |
38480 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
const int N = 5e5 + 10;
const int sq = 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;
ll seg[4*N], m, cnt[N];
int n, k, f[N];
bool last[N];
vector<ll> ind[N], v;
vector<pair<ll, int>> all;
ll get(int l, int r, int b = 0, int e = k, int id = 1)
{
if(r <= b || e <= l)
return 1;
if(l <= b && e <= r)
return seg[id];
int mid = (b + e) / 2;
return (get(l, r, b, mid, id*2) * get(l, r, mid, e, id*2+1))%m;
}
void upd(int x, ll val, int b = 0, int e = k, int id = 1)
{
if(b + 1 == e)
{
seg[id] = val%m;
return;
}
int mid = (b + e) / 2;
if(x < mid)
upd(x, val, b, mid, id*2);
else
upd(x, val, mid, e, id*2+1);
seg[id] = (seg[id*2] * seg[id*2+1]) % m;
}
inline void add(int r)
{
cnt[f[r]]++;
upd(f[r], cnt[f[r]]);
}
inline int find(ll p)
{
p = all[p].f;
int l = 0, r = k;
while(l + 1 < r)
{
int mid = (l + r) / 2;
ll len = v[mid];
if(len >= 2ll*p)
l = mid;
else
r = mid;
}
return r;
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k >> m;
//m = mod;
for(int i = 0; i < n; i++)
{
ll l, c;
cin >> l >> c;
all.push_back({l, c});
f[c] = -1;
}
sort(all.begin(), all.end());
reverse(all.begin(), all.end());
//cout << "////////" << endl;
for(int i = 0; i < n; i++)
{
int c = all[i].s;
ind[c].push_back(i);
if(f[c] == -1)
{
f[c] = v.size();
v.push_back(all[i].f);
//cout << c << ' ' << f[c] << ' ' << all[i].f << endl;
add(c);
last[i] = true;
}
//cout << all[i].f << ' ' << c << endl;
}
//cout << "///////" << endl;
ll ans = 0;
int j = n-1;
for(int i = n-1; i >= 0; i--)
{
int c = all[i].s;
while(j >= i && all[i].f >= 2ll * all[j].f)
{
add(all[j].s);
j--;
}
if(!last[i])
continue;
int x = upper_bound(ind[c].begin(), ind[c].end(), j) - ind[c].begin();
x--;
x = ind[c][x];
x = find(x);
ll p1 = get(f[c]+1, k), p2 = get(x, f[c]);
ll t = (cnt[f[c]] - 1);
ll res = (p1 * t)%m + (p1 * p2)%m;
//cout << p1 << ' ' << p2 << ' ' << t << ' ' << res << endl << endl;
ans = (ans + res) % m;
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
12140 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12268 KB |
Output is correct |
2 |
Incorrect |
11 ms |
12140 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
12140 KB |
Output is correct |
2 |
Incorrect |
184 ms |
26064 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
12160 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
12268 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
96 ms |
18908 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
12268 KB |
Output is correct |
2 |
Correct |
12 ms |
12396 KB |
Output is correct |
3 |
Incorrect |
13 ms |
12396 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
21672 KB |
Output is correct |
2 |
Incorrect |
255 ms |
26192 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
255 ms |
26576 KB |
Output is correct |
2 |
Incorrect |
245 ms |
27088 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
21972 KB |
Output is correct |
2 |
Incorrect |
252 ms |
27216 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
246 ms |
26192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
291 ms |
28376 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
240 ms |
25296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
680 ms |
34940 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
455 ms |
35764 KB |
Output is correct |
2 |
Incorrect |
532 ms |
32720 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
779 ms |
38480 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |