# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
653245 |
2022-10-26T09:48:55 Z |
Vladth11 |
Fish (IOI08_fish) |
C++11 |
|
1556 ms |
60704 KB |
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int bSize = 11;
const int bits = 23;
const int NMAX = 500001;
int MOD;
int dm;
class Aint {
public:
int aint[NMAX * 4];
void init() {
for(int i = 0; i < NMAX * 4; i++)
aint[i] = 1;
}
void add(int node, int st, int dr, int l, int x) {
if(st == dr) {
aint[node] += x;
aint[node] = max(aint[node], 1);
return;
}
int mid = (st + dr) / 2;
if(l <= mid) {
add(node * 2, st, mid, l, x);
} else {
add(node * 2 + 1, mid + 1, dr, l, x);
}
aint[node] = aint[node * 2] * aint[node * 2 + 1];
aint[node] %= MOD;
}
int query(int node, int st, int dr, int a, int b){
if(a <= st && dr <= b)
return aint[node];
int mid = (st + dr) / 2;
int prod = 1;
if(a <= mid){
prod *= query(node * 2, st, mid, a, b);
prod %= MOD;
}
if(b > mid){
prod *= query(node * 2 + 1, mid + 1, dr, a, b);
prod %= MOD;
}
return prod;
}
void update(int node, int st, int dr, int l, int x) {
if(st == dr) {
dm = aint[node];
aint[node] = x;
//aint[node] = max(aint[node], 1);
return;
}
int mid = (st + dr) / 2;
if(l <= mid) {
update(node * 2, st, mid, l, x);
} else {
update(node * 2 + 1, mid + 1, dr, l, x);
}
aint[node] = aint[node * 2] * aint[node * 2 + 1];
aint[node] %= MOD;
}
} aint, banned;
int imp[NMAX];
int col[NMAX];
int maxi[NMAX];
pii v[NMAX];
int f[NMAX];
pii cine[NMAX];
vector <int> g[NMAX];
int afla(int x, int col){
int r = -1;
int pas = (1 << bits);
while(pas){
if(r + pas < g[col].size() && g[col][r + pas] * 2 <= x)
r += pas;
pas /= 2;
}
return r;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k, i;
cin >> n >> k >> MOD;
for(i = 1; i <= n; i++) {
cin >> v[i].first >> v[i].second;
g[v[i].second].push_back(v[i].first);
}
sort(v + 1, v + n + 1);
for(i = n; i >= 1; i--) {
if(!col[v[i].second]) {
imp[i] = 1;
}
col[v[i].second]++;
}
int cnt = 0;
for(i = 1; i <= n; i++){
if(imp[i]){
cine[++cnt] = v[i];
f[cine[cnt].second] = cnt;
}
}
aint.init();
banned.init();
for(i = 1; i <= n; i++){
sort(g[i].begin(), g[i].end());
maxi[i] = col[i];
if(!f[i]) continue;
aint.update(1, 1, n, f[i], col[i] + 1);
banned.update(1, 1, n, f[i], col[i] + 1);
}
int dr = n, st = n;
int rez = 0;
for(i = n; i >= 1; i--){
while(st >= 1 && v[st].first * 2 > v[i].first){
aint.add(1, 1, n, f[v[st].second], -1);
banned.add(1, 1, n, f[v[st].second], -1);
col[v[st].second]--;
st--;
}
if(i == n){
for(int j = 1; j <= n; j++){
maxi[j] = col[j];
}
}
if(imp[i]){
if(i != n){
aint.update(1, 1, n, f[v[i].second], 1);
int r = f[v[i].second];
int pas = (1 << bits);
while(pas){
if(r + pas <= k && v[i].first * 2 > cine[r + pas].first && col[v[i].second] - 1 == afla(cine[r + pas].first, v[i].second))
r += pas;
pas /= 2;
}
rez += aint.query(1, 1, n, 1, r);
aint.update(1, 1, n, f[v[i].second], col[v[i].second] + 1);
banned.add(1, 1, n, f[v[i].second], -1);
rez %= MOD;
}
if(col[v[i].second] > 0 || i == n) /// avem frecventa mai mare ca 1..0
rez += banned.aint[1];
rez %= MOD;
banned.update(1, 1, n, f[v[i].second], 1);
}
}
cout << rez;
return 0;
}
Compilation message
fish.cpp: In function 'int afla(int, int)':
fish.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if(r + pas < g[col].size() && g[col][r + pas] * 2 <= x)
| ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp: In function 'int main()':
fish.cpp:130:9: warning: unused variable 'dr' [-Wunused-variable]
130 | int dr = n, st = n;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
27732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27732 KB |
Output is correct |
2 |
Correct |
14 ms |
27720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
27732 KB |
Output is correct |
2 |
Correct |
328 ms |
36032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
27768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
27860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
31384 KB |
Output is correct |
2 |
Correct |
156 ms |
32140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
27860 KB |
Output is correct |
2 |
Correct |
18 ms |
27860 KB |
Output is correct |
3 |
Correct |
17 ms |
27860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
192 ms |
33356 KB |
Output is correct |
2 |
Incorrect |
361 ms |
36128 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
321 ms |
37428 KB |
Output is correct |
2 |
Correct |
336 ms |
36892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
188 ms |
34728 KB |
Output is correct |
2 |
Correct |
342 ms |
36652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
373 ms |
36524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
395 ms |
37876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
379 ms |
36144 KB |
Output is correct |
2 |
Correct |
615 ms |
41912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
668 ms |
42076 KB |
Output is correct |
2 |
Correct |
539 ms |
39880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
548 ms |
43184 KB |
Output is correct |
2 |
Correct |
695 ms |
41804 KB |
Output is correct |
3 |
Correct |
708 ms |
46072 KB |
Output is correct |
4 |
Correct |
614 ms |
41884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
849 ms |
45036 KB |
Output is correct |
2 |
Correct |
1240 ms |
59520 KB |
Output is correct |
3 |
Correct |
1556 ms |
60704 KB |
Output is correct |
4 |
Correct |
1402 ms |
54404 KB |
Output is correct |