Submission #776564

#TimeUsernameProblemLanguageResultExecution timeMemory
776564salmonFish (IOI08_fish)C++14
49 / 100
3072 ms65536 KiB
#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)

fish.cpp: In function 'int main()':
fish.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
fish.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    for(int j = 0; j < oh.size(); j++){
      |                   ~~^~~~~~~~~~~
fish.cpp:20:7: warning: variable 'visited' set but not used [-Wunused-but-set-variable]
   20 |  bool visited[M + 1];
      |       ^~~~~~~
fish.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf(" %d",&N);
      |  ~~~~~^~~~~~~~~~
fish.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf(" %d",&M);
      |  ~~~~~^~~~~~~~~~
fish.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf(" %d",&mod);
      |  ~~~~~^~~~~~~~~~~~
fish.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf(" %d",&l);
      |   ~~~~~^~~~~~~~~~
fish.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf(" %d",&h);
      |   ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...