oj.uz

Submission #132066

# Submission time Handle Problem Language Result Execution time Memory
132066 2019-07-18T09:16:23 Z dragonslayerit Fish (IOI08_fish) C++14
100 / 100
 1289 ms 61336 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

//Strategy:
//Sort fishes by size
//Relabel gems by last appearance (e.g. gem of largest fish is 0)
//count multisets of gems => count multisets of fish such that if a fish is chosen, all smaller fish with same gem are chosen
//For the actual subset of fish, some gem will be chosen to be "boosted" to the largest fish with that gem.
//Iterate over last fish in multiset (pre-boosting) and count number of valid subsets
//A multiset is bad iff no gem in the prefix is present and the largest fish's gem cannot be boosted.

int N,MOD;

int cps[500005];
int cps_size=0;

int freq[500005];
int freq2[500005];
int last[500005];

int half[500005];
int prev[500005];

struct Fish{
  int size,gem;
  bool operator<(Fish f)const{
    return size<f.size;
  }
}fishes[500005];

struct Op{
  int sgn;
  int l,r,x;
  Op(int sgn,int l,int r,int x):sgn(sgn),l(l),r(r),x(x){
  }
};

std::vector<Op> ops[500005];

int st[1000010];

void pull(int i){
  st[i]=1LL*st[i<<1]*st[i<<1|1]%MOD;
}

void update(int i){
  for(st[i+=N]++;i>1;i>>=1){
    pull(i>>1);
  }
}

int query(int a,int b){
  int res=1;
  for(a+=N,b+=N;a<b;a>>=1,b>>=1){
    if(a&1) res=1LL*res*st[a++]%MOD;
    if(b&1) res=1LL*res*st[--b]%MOD;
  }
  return res;
}

int main(){
  int K;
  scanf("%d %d",&N,&K);
  scanf("%d",&MOD);
  for(int i=0;i<N;i++){
    scanf("%d %d",&fishes[i].size,&fishes[i].gem);
    fishes[i].gem--;
  }
  std::sort(fishes,fishes+N);
  //Relabel gems by last appearance
  std::fill(cps,cps+K,-1);
  for(int i=N-1;i>=0;i--){
    if(cps[fishes[i].gem]==-1){
      cps[fishes[i].gem]=cps_size++;
    }
  }
  for(int i=0;i<N;i++){
    fishes[i].gem=cps[fishes[i].gem];
  }
  for(int k=0;k<K;k++){
    last[k]=-1;
  }
  for(int i=0;i<N;i++){
    prev[i]=last[fishes[i].gem];
    last[fishes[i].gem]=i;
  }
  for(int k=0;k<K;k++){
    int low=-1,high=N;
    while(high-low>1){
      int mid=(low+high)/2;
      if(fishes[mid].size*2<=fishes[last[k]].size){
	low=mid;
      }else{
	high=mid;
      }
    }
    half[k]=high;
    //half[k] is index of first fish larger than fishes[last[k]].size/2
  }
  
  int prefix=K-1;//largest gem # that can be "boosted"
  for(int i=0;i<N;i++){
    //Counting configurations where fishes[i].gem occurs exactly freq[fishes[i].gem] times
    while(prefix>=0&&fishes[last[prefix]].size<2*fishes[i].size) prefix--;
    //Subtract multisets where none in prefix exist to be boosted
    ops[i+1].emplace_back(-1,prefix+1,K,fishes[i].gem);
    //Add back multisets where none in prefix exist to be boosted but fishes[i] can be boosted
    //Must be able to take all of fishes[i].gem before i
    if(prev[i]==-1||fishes[prev[i]].size*2<=fishes[last[fishes[i].gem]].size){
      //Cannot have fish whose size <=1/2*size of last fish with fishes[i].gem
      ops[std::min(i,half[fishes[i].gem])].emplace_back(1,prefix+1,K,fishes[i].gem);
    }
  }
  //Count all
  ops[N].emplace_back(1,0,K,-1);
  //init st
  std::fill(st,st+N*2,1);
  //-1 for empty set
  int ans=-1;
  for(int i=0;i<=N;i++){
    for(Op op:ops[i]){
      int product=1;
      /*
      for(int k=op.l;k<op.r;k++){
	if(k==op.x) continue;
	product=1LL*product*(freq[k]+1)%MOD;
      }
      */
      if(op.x>=op.l&&op.x<op.r){
	product=1LL*query(op.l,op.x)*query(op.x+1,op.r)%MOD;
      }else{
	product=1LL*query(op.l,op.r);
      }
      ans=(ans+op.sgn*product)%MOD;
    }
    if(i==N) break;
    freq[fishes[i].gem]++;
    update(fishes[i].gem);
  }
  printf("%d\n",(ans+MOD)%MOD);
  return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&K);
   ~~~~~^~~~~~~~~~~~~~~
fish.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&MOD);
   ~~~~~^~~~~~~~~~~
fish.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&fishes[i].size,&fishes[i].gem);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12024 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12196 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 13 ms 12124 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12092 KB Output is correct
2 Correct 465 ms 41720 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12280 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 23656 KB Output is correct
2 Correct 234 ms 26988 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12280 KB Output is correct
2 Correct 21 ms 12536 KB Output is correct
3 Correct 20 ms 12432 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 29944 KB Output is correct
2 Correct 512 ms 48504 KB Output is correct
3 Correct 548 ms 48708 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 44664 KB Output is correct
2 Correct 561 ms 48892 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 27616 KB Output is correct
2 Correct 596 ms 48928 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 39424 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 42004 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 36328 KB Output is correct
2 Correct 900 ms 48508 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 42892 KB Output is correct
2 Correct 671 ms 39096 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 44532 KB Output is correct
2 Correct 1002 ms 51572 KB Output is correct
3 Correct 951 ms 56548 KB Output is correct
4 Correct 924 ms 52344 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 47588 KB Output is correct
2 Correct 1142 ms 60484 KB Output is correct
3 Correct 1153 ms 61336 KB Output is correct
4 Correct 1289 ms 60636 KB Output is correct