Submission #1221197

#TimeUsernameProblemLanguageResultExecution timeMemory
1221197m5588ohammedFish (IOI08_fish)C++20
0 / 100
318 ms14928 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" int n,k,mod; const int N=(1<<19); int fre[500001],vis[500001],curr=1,curr2=1,ans=0,mx[500001]; array<int,2> arr[500001]; int Tree[N*2+5][2]; void update(int i,int u,int val){ i+=N; val%=mod; Tree[i][u]=val; i/=2; while(i!=0){ //cout<<Tree[i*2+1][u]<<" "<<Tree[i*2][u]<<endl; Tree[i][u]=(Tree[i*2+1][u]*Tree[i*2][u])%mod; i/=2; } curr=Tree[1][0]; curr2=Tree[1][1]; //cout<<"! "<<curr<<" "<<val<<endl; return; } void ins(int i){ fre[i]++; update(i,0,fre[i]); update(i,1,fre[i]); return; } void ers(int i){ fre[i]--; if(vis[i]==0) update(i,1,fre[i]); update(i,0,fre[i]); return; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>k>>mod; for(int i=0;i<N*2+5;i++) Tree[i][0]=Tree[i][1]=1; for(int tp=1;tp<=k;tp++) fre[tp]=1; for(int i=0;i<n;i++){ cin>>arr[i][0]>>arr[i][1]; ins(arr[i][1]); } sort(arr,arr+n); curr2=curr; int lst=n-1; for(int i=n-1;i>=0;i--){ while(lst>=0&&arr[lst][0]*2>arr[i][0]){ ers(arr[lst][1]); lst--; } if(vis[arr[i][1]]==1) continue; vis[arr[i][1]]=1; if(i==n-1){ for(int tp=1;tp<=k;tp++) mx[tp]=fre[tp]; } if(n-1!=i&&fre[arr[i][1]]!=1&&fre[arr[i][1]]==mx[arr[i][1]]){ update(arr[i][1],0,1); ans+=curr; ans%=mod; update(arr[i][1],0,fre[arr[i][1]]); } ans+=curr2; ans%=mod; update(arr[i][1],1,1); } cout<<ans<<endl; return 0; }
#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...