# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
776564 | salmon | Fish (IOI08_fish) | C++14 | 3072 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int N,M;
int mod;
int l,h;
const int sq = 200;
vector<pair<int,int>> v;
long long int pown[sq + 5][500100];
int main(){
scanf(" %d",&N);
scanf(" %d",&M);
scanf(" %d",&mod);
map<int,int> mep;
set<int> one;
map<int,int> mepu;
set<int> oneu;
bool visited[M + 1];
bool usable[M + 1];
for(int j = 1; j <= sq + 1; j++){
pown[j][0] = 1;
for(int i = 1; i <= M; i++){
pown[j][i] = pown[j][i - 1] * j % mod;
}
}
for(int i = 0; i <= M; i++){
visited[i] = false;
}
for(int i = 0; i <= M; i++) usable[i] = false;
for(int i = 0; i < N; i++){
scanf(" %d",&l);
scanf(" %d",&h);
v.push_back(make_pair(l,h));
}
sort(v.begin(),v.end(),greater<pair<int,int>>());
set<int> o;
set<int> smol;
vector<pair<int,int>> oh;
for(int i = 0; i < v.size(); i++){
if(o.find(v[i].second) == o.end()){
oh.push_back(v[i]);
o.insert(v[i].second);
}
}
int it = 0;
reverse(v.begin(),v.end());
int bigans = 0;
vector<pair<int,int>> tempuse;
for(int i = 0; i < N; i++){
while(it != N && v[i].first >= v[it].first * 2){
if(usable[v[it].second]){
if(one.find(v[it].second) != one.end() && mep.find(v[it].second) == mep.end()){
one.erase(v[it].second);
mep[v[it].second] = 2;
}
else if(mep.find(v[it].second) == mep.end()){
one.insert(v[it].second);
}
else{
mep[v[it].second]++;
}
it++;
}
else{
if(oneu.find(v[it].second) != oneu.end() && mepu.find(v[it].second) == mepu.end()){
oneu.erase(v[it].second);
mepu[v[it].second] = 2;
}
else if(mepu.find(v[it].second) == mepu.end()){
oneu.insert(v[it].second);
}
else{
mepu[v[it].second]++;
}
it++;
}
}
if(v[i] == oh.back()){
if(mepu.find(oh.back().second) != mepu.end()){
mep[oh.back().second] = mepu[oh.back().second];
}
else if(oneu.find(oh.back().second) != oneu.end()){
one.insert(oh.back().second);
}
usable[oh.back().second] = true;
long long int ans = pown[2][one.size()];
for(pair<int,int> ii : mep){
ans = ans * (ii.second + 1) % mod;
}
bigans += ans;
bigans %= mod;
oh.pop_back();
long long int sub = 1;
ans = 1;
for(int j = 0; j < oh.size(); j++){
if(oh[j].first < v[i].first * 2){
bool flag = false;
for(int k = it; k < i; k++){
if(oh[j].first >= v[k].first * 2 && v[k].second == v[i].second) flag = true;
}
if(flag) continue;
if(oneu.find(oh[j].second) != oneu.end()){
ans *= 2;
ans %= mod;
}
else if(mepu.find(oh[j].second) != mepu.end()){
ans *= (1 + mepu[oh[j].second]);
ans %= mod;
}
}
}
if(one.find(v[i].second) == one.end()){
ans *= pown[2][one.size()];
sub *= pown[2][one.size()];
}
else{
ans *= pown[2][one.size() - 1];
sub *= pown[2][one.size() - 1];
}
ans %= mod;
sub %= mod;
for(pair<int,int> ii : mep){
if(ii.first != v[i].second) ans = ans * (ii.second + 1) % mod;
if(ii.first != v[i].second) sub = sub * (ii.second + 1) % mod;
}
ans -= sub;
ans =(ans + mod) % mod;
bigans += ans;
bigans %= mod;
//printf("%d %d %d %d\n",v[i].first,bigans,ans,sub);
}
}
printf("%d",bigans);
}
/*
*
5
3
700
8 3
7 2
4 1
2 3
2 2
*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |