oj.uz

Submission #303933

# Submission time Handle Problem Language Result Execution time Memory
303933 2020-09-20T19:35:01 Z Hemimor Fish (IOI08_fish) C++14
100 / 100
 557 ms 19832 KB 
#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]=(date[k]+x+mod)%mod;
		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);
		if(c[i]<inf){
			(res+=x*st.Query(i+1,c[i]+1))%=mod;
			(res+=x*(st.Open(i)-1))%=mod;
		}
		else (res+=x*st.Open(i))%=mod;
	}
	printf("%d\n",res);
}

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6400 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6432 KB Output is correct
2 Correct 255 ms 10304 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6400 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6528 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8032 KB Output is correct
2 Correct 123 ms 8336 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6400 KB Output is correct
2 Correct 7 ms 6528 KB Output is correct
3 Correct 7 ms 6400 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8776 KB Output is correct
2 Correct 286 ms 10360 KB Output is correct
3 Correct 244 ms 17224 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 10364 KB Output is correct
2 Correct 244 ms 10360 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 8828 KB Output is correct
2 Correct 253 ms 10360 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 10224 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 10616 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 10360 KB Output is correct
2 Correct 356 ms 11896 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 12284 KB Output is correct
2 Correct 263 ms 11256 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 12408 KB Output is correct
2 Correct 366 ms 11896 KB Output is correct
3 Correct 375 ms 13560 KB Output is correct
4 Correct 361 ms 19832 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 13432 KB Output is correct
2 Correct 472 ms 18104 KB Output is correct
3 Correct 557 ms 18168 KB Output is correct
4 Correct 528 ms 16632 KB Output is correct