Submission #303926

#	Time	Username	Problem	Language	Result	Execution time	Memory
303926		Hemimor	Fish (IOI08_fish)	C++14	88 / 100	538 ms	26488 KiB

fish

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
//const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int mod;

class Segment_Tree{
	private:
	int n;
	vi date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]*date[k*2+2]%mod;
		}
	}
	int Query(int a,int b){
		a+=n-1;b+=n-1;
		int m=1;
		while(a<b){
			if(a%2==0) (m*=date[a++])%=mod;
			if(b%2==0) (m*=date[--b])%=mod;
			a/=2;b/=2;
		}
		return m;
	}
	int Open(int k){return date[k+n-1];}
};

const int M=500001;
int n,m,c[M],perm[M];
P a[M];
pip b[M];
Segment_Tree st(M);

int main(){
	scanf("%d%d%d",&m,&n,&mod);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		y--;
		a[i]={x,y};
		b[y].first=max(b[y].first,x);
		b[y].second.first++;
		b[y].second.second=y;
	}
	sort(a,a+m);sort(b,b+n);
	fill(c,c+M,inf);
	for(int i=0;i<n;i++){
		st.Update(i,b[i].second.first+1);
		perm[b[i].second.second]=i;
	}
	int I=m-1,res=0;
	for(int i=n-1;i>=0;i--){
		while(I>=0&&a[I].first*2>b[i].first){
			int id=perm[a[I].second];
			st.Update(id,-1);
			c[id]=i;
			I--;
		}
		int x=st.Query(0,i),t=c[perm[b[i].second.second]];
		if(t<inf){
			(res+=x*st.Query(i+1,t+1))%=mod;
			(res+=x*(st.Open(i)-1))%=mod;
		}
		else (res+=x*st.Open(i))%=mod;
	}
	printf("%d\n",res);
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |  scanf("%d%d%d",&m,&n,&mod);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 0 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 0 / 5
• Subtask 19: 5 / 5