oj.uz

Submission #1104081

# Submission time Handle Problem Language Result Execution time Memory
1104081 2024-10-22T16:38:11 Z _rain_ Fish (IOI08_fish) C++14
100 / 100
 491 ms 46152 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define name "main"
typedef long long ll;
 
const int N = (int)5e5;
struct Node{
	int len;
	int gem;
	bool operator < (const Node& other) const{
		return len < other.len;
	}
} p[N+2];
int n,k,MOD;
	int add(int a , int b){
		return a + b >= MOD ? a + b - MOD : a + b;
	}
	int sub(int a,int b){
		return a - b < 0 ? a - b + MOD : a - b;
	}
	int mul(int a, int b){
		return (ll)a*b%MOD;
	}
int id[N+2];
bool last[N+2]={},vis[N+2]={};
int b[N+2],c[N+2],sl[N+2]={};
vector<int> bag[N+2];
int st[N*4+2];
#define lef(id) id*2
#define rig(id) id*2+1
void build(int id,int l,int r){
	if (l==r) st[id]=1;
	else{
		int m=l+r>>1;
		build(lef(id),l,m);
		build(rig(id),m+1,r);
		st[id]=1;
	}
	return;
}
void upd(int id,int l,int r,int pos,int t){
	if (l>pos||r<pos) return;
	if (l==r){
		st[id] = add(st[id],t);
	}
	else{
		int m=l+r>>1;
		if (l<=m) upd(lef(id),l,m,pos,t);
		if (m<r) upd(rig(id),m+1,r,pos,t);
		st[id]=mul(st[lef(id)],st[rig(id)]);
	}
	return;
}
int Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 1;
	if (u<=l&&r<=v) return st[id];
	int m=l+r>>1;
	return mul(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n>>k>>MOD;
	for (int i = 1; i <= n; ++i){
		cin>>p[i].len>>p[i].gem;
	}
	sort(p+1,p+n+1);
	int cnt=0;
	for (int i = n; i >= 1; --i){
		if (!vis[p[i].gem]) {
			last[i] = true;
			vis[p[i].gem] = true;
		}
	}
	for (int i = 1; i <= n;++i){
		if (last[i]) {
			id[p[i].gem]=++cnt;
			b[cnt]=p[i].len;
		}
		bag[p[i].gem].push_back(p[i].len);
	}
	build(1,1,cnt);
	int ans=0;
	for (int i = 1 , l = 1; i <= n; ++i){
		while (l<=i&&p[l].len*2<=p[i].len){
			upd(1,1,cnt,id[p[l].gem],1);
			c[p[l].gem]=add(c[p[l].gem],1);
			sl[p[l].gem]++;
			++l;
		}
		if (last[i]){
			int l=id[p[i].gem]+1,r=cnt;
			int x=p[i].gem;
			while(l<=r){
				int m=l+r>>1;
				int lime=upper_bound(bag[x].begin(),bag[x].end(),b[m]/2)-bag[x].begin();
				if (lime<=sl[x]) l=m+1;
				else r=m-1;
			}
			ans = add(ans,mul(Get(1,1,cnt,1,id[x]-1),add(Get(1,1,cnt,id[x]+1,l-1),c[x])));
		}
	}
	cout<<ans;
	exit(0);
}

Compilation message

fish.cpp: In function 'void build(int, int, int)':
fish.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m=l+r>>1;
      |         ~^~
fish.cpp: In function 'void upd(int, int, int, int, int)':
fish.cpp:48:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int m=l+r>>1;
      |         ~^~
fish.cpp: In function 'int Get(int, int, int, int, int)':
fish.cpp:58:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int m=l+r>>1;
      |        ~^~
fish.cpp: In function 'int32_t main()':
fish.cpp:98:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     int m=l+r>>1;
      |           ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct
2 Correct 3 ms 18768 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18768 KB Output is correct

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22088 KB Output is correct
2 Correct 63 ms 22240 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19024 KB Output is correct
2 Correct 5 ms 18884 KB Output is correct
3 Correct 4 ms 19024 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 23020 KB Output is correct
2 Correct 138 ms 24732 KB Output is correct
3 Correct 158 ms 31440 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 25320 KB Output is correct
2 Correct 137 ms 25328 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 23112 KB Output is correct
2 Correct 150 ms 25056 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 25168 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 28144 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 26968 KB Output is correct
2 Correct 183 ms 30180 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 30792 KB Output is correct
2 Correct 219 ms 29416 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 31716 KB Output is correct
2 Correct 277 ms 30700 KB Output is correct
3 Correct 303 ms 34656 KB Output is correct
4 Correct 250 ms 30704 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 32884 KB Output is correct
2 Correct 491 ms 46152 KB Output is correct
3 Correct 401 ms 44268 KB Output is correct
4 Correct 482 ms 42312 KB Output is correct